Описание
Метод сортировки пузырьком основан на попарном сравнении соседних элементов в массиве. При каждом из проходов каждый из элементов попарно сравниваются с следующим из ним элементом в массиве. При сравнении, если текущий элемент больше следующего, то эти элементы меняются местами. Проходы выполняют для всех элементов в массиве, либо пока все элементы не будут отсортированы.
Временная сложность алгоритма
В худшем случае выполняется N проходов. В каждом проходе в худшем случае выполняется N-1 сравнений.
Возможно оптимизировать количество сравнений в каждом проходе. После каждого прохода, в конце неотсортированной части массива оказывается максимальное значение в неотсортированной части. Таким образом на каждом из следующих проходов можно сократить количество сравнений на один.
С учетом оптимизации временная сложность алгоритма будет равна 1/2*n^2 - O(n^2).
Пространственная сложность алгоритма
В ходе выполнения алгоритма, все преобразования выполняются над оригинальным массивом. Пространственная сложность алгоритма равна O(n).
Реализация алгоритма
Ниже приведен пример реализации алгоритма на языке Python.
def bubble_sort(array):
# Выполняем N проходов для массиса длиной N
for i in range(len(array) - 1, 0, -1):
# Выполняем сравнения для всех элементов на неотсортированной части массива
for j in range(i):
# В случае если текущий элемент больше следующего, меняем их местами
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array