Визуализация сортировки пузырьком

Что такое алгоритм сортировки пузырьком?

Пузырьковая сортировка — это простой и неэффективный алгоритм сортировки, который многократно сравнивает соседние элементы. в списке и меняет их местами, если они находятся в неправильном порядке. Этот процесс продолжается до тех пор, пока весь список сортируется. При каждом проходе по списку самый большой (или самый маленький) элемент постепенно «пузырится» вверх. в правильное положение. Пузырьковая сортировка проста для понимания и реализации, но, как правило, работает плохо. в больших или уже отсортированных списках.

Пузырьковая сортировка, иногда называемая сортировкой погружением, представляет собой простой алгоритм сортировки, который многократно проходит по входному списку элемент за элементом, сравнивая текущий элемент с последующим, при необходимости меняя их значения. Эти проходы по списку повторяются до тех пор, пока во время прохода не нужно будет выполнять перестановки, что означает, что список стал полностью отсортированным. Алгоритм, представляющий собой сортировку сравнением, назван в честь того, как более крупные элементы «всплывают» вверх списка.

Этот простой алгоритм плохо работает в реальном мире и используется в основном как образовательный инструмент. Более эффективные алгоритмы, такие как quicksort, timsort или сортировка слиянием, используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java. Однако, если параллельная обработка разрешена, пузырьковая сортировка выполняется за время O(n), что делает ее значительно быстрее, чем параллельные реализации сортировки вставками или сортировки выбором, которые не так эффективно распараллеливают.

Реализация на JavaScript

  function bubbleSort(arr) {
    const length = arr.length;

    for (let i = 0; i < length - 1; i++) {
      for (let j = 0; j < length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          // Swap the elements
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }

    return arr;
  }

Реализация на Go / Golang

  func bubbleSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n-1; i++ {
      for j := 0; j < n-i-1; j++ {
        if arr[j] > arr[j+1] {
          arr[j], arr[j+1] = arr[j+1], arr[j]
        }
      }
    }
    return arr
  }

Реализация на Python

  def bubble_sort(arr):
      n = len(arr)
      for i in range(n - 1):
          for j in range(n - i - 1):
              if arr[j] > arr[j + 1]:
                  arr[j], arr[j + 1] = arr[j + 1], arr[j]

Source: Wikipedia