Пузырьковая сортировка – это популярный, но неэффективный алгоритм сортировки, который легко уступает другим алгоритмам сортировки, таким как сортировка вставкой или быстрая сортировка. Алгоритм принимает неупорядоченную последовательность чисел на входе и производит отсортированную последовательность чисел на выходе.
Идея алгоритма проста: несколько раз сравнивайте соседние элементы в массиве и меняйте их местами, если они не отсортированы. Алгоритм повторяет описанный выше процесс до тех пор, пока все элементы в массиве не будут отсортированы. На каждой итерации алгоритма алгоритм сравнивает все пары соседних элементов. Смежные элементы меняются местами, если они не отсортированы.
Пример:
Пусть исходный массив будет [5, 4, 9, 3, 7, 6].
Первая итерация:
сравните элементы в индексах 1 и 2: 5, 4. Они не отсортированы. Поменяйте их местами. Array = [4, 5, 9, 3, 7, 6].
Сравните элементы в индексе 2 и 3: 5, 9. Они отсортированы. Не меняйте местами. Array = [4, 5, 9, 3, 7, 6].
Сравните элементы в индексе 3 и 4: 9, 3. Они не отсортированы. Поменяйте их местами. Array = [4, 5, 3, 9, 7, 6].
Сравните элементы в индексе 4 и 5: 9, 7. Они не отсортированы. Поменяйте их местами. Array = [4, 5, 3, 7, 9, 6].
Сравните элементы в индексе 5 и 6: 9, 6. Они не отсортированы. Поменяйте их местами. Array = [4, 5, 3, 7, 6, 9]
Массив после первой итерации равен [4, 5, 3, 7, 6, 9].
В таблице ниже описан полный процесс сортировки, включая другие итерации. Для краткости показаны только шаги, на которых происходит замена.
Первая итерация:
[5, 4, 9, 3, 7, 6]
[4, 5, 9, 3, 7, 6]
[4, 5, 3, 9, 7, 6]
[4, 5, 3, 7 , 9, 6]
[4, 5, 3, 7, 6, 9]
Вторая итерация:
[4, 3, 5, 7, 6, 9]
[4, 3, 5, 6, 7, 9]
Третья итерация:
[3, 4, 5, 6, 7, 9]
Исходный код: пузырьковая сортировка
def bubble_sort(arr, n): for i in range(0, n): for j in range(0, n-1): # Если пара не находится в отсортированном порядке if arr[j] > arr[j+1]: # Поменяйте местами пары, чтобы сделать их в отсортированном порядке arr[j], arr[j+1] = arr[j+1], arr[j] return arr if __name__ == "__main__": arr = [5, 4, 9, 7, 3, 6] n = len(arr) arr = bubble_sort(arr, n) print (arr)
Пояснение: Алгоритм состоит из двух циклов. Первый цикл повторяется по массиву n раз, а второй цикл n-1 раз. На каждой итерации первого цикла второй цикл сравнивает все пары соседних элементов. Если они не отсортированы, соседние элементы меняются местами, чтобы упорядочить их. Максимальное количество сравнений, необходимых для присвоения элементу его правой позиции в отсортированном порядке, равно n-1, потому что есть n-1 других элементов. Так как имеется n элементов, и каждый элемент требует максимум n-1 сравнений; массив сортируется за время O (n ^ 2). Следовательно, временная сложность наихудшего случая равна O (n ^ 2). Лучшая временная сложность в этой версии пузырьковой сортировки также составляет O (n ^ 2), потому что алгоритм не знает, что он полностью отсортирован. Следовательно, даже если он отсортирован.
Часть 2 (необязательно): оптимизированная пузырьковая сортировка
Вышеупомянутый алгоритм можно оптимизировать, если мы сможем остановить сравнение, когда все элементы будут отсортированы. Это можно сделать с помощью дополнительной переменной-флага, которая сообщает алгоритму, когда следует остановиться.
def optimised_bubble_sort(arr, n): not_sorted = True while(not_sorted): not_sorted = False for i in range(0, n-1): # Если пара не находится в отсортированном порядке if arr[i] > arr[i+1]: # Поменяйтесь ими местами arr[i], arr[i+1] = arr[i+1], arr[i] # Помните, что массив не был отсортирован # в начале итерации not_sorted = True return arr if __name__ == "__main__": arr = [5, 4, 9, 7, 3, 6] n = len(arr) arr = optimised_bubble_sort(arr, n) print (arr)
В приведенном выше алгоритме флаговая переменная not_sorted остается истинной, пока происходит обмен в итерации внутреннего цикла for. Эта оптимизированная версия пузырьковой сортировки требует одной дополнительной итерации после сортировки массива, чтобы проверить, отсортирован ли массив или нет.
Оптимальная временная сложность этого алгоритма – O (n). Это происходит, когда все элементы входного массива уже находятся в отсортированном порядке, и требуется одна итерация, чтобы проверить, находится ли массив в отсортированном порядке или нет.