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

Идея алгоритма проста: несколько раз сравнивайте соседние элементы в массиве и меняйте их местами, если они не отсортированы. Алгоритм повторяет описанный выше процесс до тех пор, пока все элементы в массиве не будут отсортированы. На каждой итерации алгоритма алгоритм сравнивает все пары соседних элементов. Смежные элементы меняются местами, если они не отсортированы.

Пример:

Пусть исходный массив будет [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)

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)