Сортировка пузырьком (Bubble Sort)

Конечно, вот описание сортировки пузырьком, переделанное в вики-разметку:

Описание

Сортировка пузырьком — это простой алгоритм сортировки, который многократно проходит по списку, сравнивая соседние элементы и меняя их местами, если они находятся в неправильном порядке. Элементы с большими значениями постепенно "всплывают" к концу списка, как пузырьки в воде, отсюда и название алгоритма.

Принцип работы

1. Сравнение соседних элементов: Алгоритм начинает с первого элемента списка и сравнивает его со вторым элементом.
2. Обмен элементов: Если первый элемент больше второго, они меняются местами.
3. Проход по списку: Этот процесс повторяется для каждой пары соседних элементов до конца списка. В результате самого большого элемента "всплывает" в конец списка.
4. Повторение процесса: Шаги 1-3 повторяются для оставшейся части списка (исключая последний элемент, который уже отсортирован).
5. Завершение: Процесс повторяется до тех пор, пока не будут отсортированы все элементы списка.

Сравнение соседних элементов

Алгоритм начинает с первого элемента списка и сравнивает его со вторым элементом.

Обмен элементов

Если первый элемент больше второго, они меняются местами.

Проход по списку

Этот процесс повторяется для каждой пары соседних элементов до конца списка. В результате самого большого элемента "всплывает" в конец списка.

Повторение процесса

Шаги 1-3 повторяются для оставшейся части списка (исключая последний элемент, который уже отсортирован).

Завершение

Процесс повторяется до тех пор, пока не будут отсортированы все элементы списка.

Пример

Пусть у нас есть следующий список: [5, 1, 4, 2, 8]

1. Первый проход:
   1. (5, 1, 4, 2, 8) → (1, 5, 4, 2, 8) (5 и 1 меняются местами)
   2. (1, 5, 4, 2, 8) → (1, 4, 5, 2, 8) (5 и 4 меняются местами)
   3. (1, 4, 5, 2, 8) → (1, 4, 2, 5, 8) (5 и 2 меняются местами)
   4. (1, 4, 2, 5, 8) → (1, 4, 2, 5, 8) (5 и 8 не меняются местами)

После первого прохода наибольший элемент (8) находится в конце списка.

1. Второй проход:
   1. (1, 4, 2, 5, 8) → (1, 4, 2, 5, 8)
   2. (1, 4, 2, 5, 8) → (1, 2, 4, 5, 8) (4 и 2 меняются местами)
   3. (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)

После второго прохода второй наибольший элемент (5) находится на своем месте.

1. Третий проход:
   1. (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)
   2. (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)

После третьего прохода третий наибольший элемент (4) находится на своем месте.

1. Четвертый проход:
   1. (1, 2, 4, 5, 8) → (1, 2, 4, 5, 8)

В результате список отсортирован: [1, 2, 4, 5, 8]

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

<syntaxhighlight lang="python"> def bubble_sort(arr):

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

1. Пример использования

arr = [5, 1, 4, 2, 8] sorted_arr = bubble_sort(arr) print(sorted_arr) # Вывод: [1, 2, 4, 5, 8] </syntaxhighlight>

Характеристики

• Простота: Легко понять и реализовать.
• Сложность:
  • Временная сложность:
    • Лучший случай: O(n) (если список уже отсортирован)
    • Средний случай: O(n^2)
    • Худший случай: O(n^2)
  • Пространственная сложность: O(1) (не требует дополнительной памяти)
• Устойчивость: Сортировка пузырьком является устойчивым алгоритмом, то есть элементы с одинаковыми значениями сохраняют свой относительный порядок после сортировки.

Оптимизация

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

<syntaxhighlight lang="python"> def optimized_bubble_sort(arr):

   n = len(arr)
   for i in range(n):
       swapped = False
       for j in range(0, n-i-1):
           if arr[j] > arr[j+1]:
               arr[j], arr[j+1] = arr[j+1], arr[j]
               swapped = True
       if not swapped:
           break  # Если не было обменов, список отсортирован
   return arr

1. Пример использования

arr = [5, 1, 4, 2, 8] sorted_arr = optimized_bubble_sort(arr) print(sorted_arr) # Вывод: [1, 2, 4, 5, 8] </syntaxhighlight>

Когда использовать

Сортировка пузырьком обычно не используется для больших объемов данных из-за своей квадратичной временной сложности. Она может быть полезна для небольших списков или в учебных целях из-за своей простоты.