Bubble sort в Python: что такое сортировка пузырьком
Алгоритм сортировки пузырьком позволяет упорядочить и отсортировать набор чисел в порядке возрастания. Почему же метод так называется?
В процессе его работы происходит попарное сравнение соседних элементов списка. Если первый элемент больше второго, то они меняются местами. Чтобы избежать сбоя или ошибки, осуществляется несколько таких проходов со сравнением элементов в массиве. Так, большие элементы постепенно передвигаются в конец списка, а меньшие — в начало. Получается некий «пузырьковый эффект», где более «легкие» элементы устремляются на поверхность, а «тяжелые» опускаются на дно.
Чтобы использовать сортировку методом пузырька, нужно воспользоваться двумя циклами:
- внешним;
- внутренним.
Во внешнем цикле количество проходов определяется длиной списка элементов минус 1, поскольку в процессе сравнения берется первое число и сравнивается с каждым из последующих.
В внутреннем цикле количество проходов зависит от номера итераций внешнего цикла, поскольку конец списка уже отсортирован и совершать проходы по этим числам нет никакого смысла.
Алгоритм сортировки пузырьком
Необходимо отсортировать следующие элементы [24, 86, 12, 9, 33]
Внешний цикл
Первый проход:
- 24 больше 86 — нет;
- 86 больше 12 — да, элементы меняются местами;
- 86 больше 9 — да, элементы меняются местами;
- 86 больше 33 — да, элементы меняются местами;
В первой итерации получаем [24, 12, 9, 33, 86].
Второй проход:
- 24 больше 12 — да, элементы меняются местами;
- 24 больше 9 — да, элементы меняются местами;
- 24 больше 33 — нет.
Во второй итерации потребуется три прохода, поскольку число 86 уже стоит на своем месте. Получаем [12, 9, 24, 33, 86].
Третий проход:
- 12 больше 9 — да, элементы меняются местами;
- 12 больше 24 — нет;
В третьей итерации потребуется два прохода, поскольку 86 и 33 стоят уже на своих местах. Получаем [9, 12, 24, 33, 86].
Четвертый проход:
- 9 больше 12 — нет.
В четвертой итерации потребуется 1 проход, поскольку остальные числа уже стоят на своих местах. Получаем [9, 12, 24, 33, 86].
Реализация bubble sort
- С помощью циклов for:
# bubble sort_for def bubble_sort(array): length = len(array) for i in range(0, length): for j in range(0, length - i - 1): if array[j] > array[j + 1]: temp = array[j] array[j] = array[j + 1] array[j + 1] = temp print("Sort") arr = [] n = int(input("Array length: ")) for i in range(0, n): element = int(input("arr[" + str(i + 1) + "] = ")) arr.append(element) bubble_sort(arr) print("Sorted array: ") print(arr)
Результат работы программы:
Sort Array length: 9 arr[1] = 9 arr[2] = 7 arr[3] = 5 arr[4] = 1 arr[5] = 4 arr[6] = 3 arr[7] = 6 arr[8] = 2 arr[9] = 8 Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9] Press any key to continue...
- С помощью циклов while
# bubble sort_while a = [] number = int(input("the Total Number of Elements : ")) for i in range(number): value = int(input("Enter %d Element of List1 : " %i)) a.append(value) i = 0 while(i < number -1): j = 0 while(j < number - i - 1): if(a[j] > a[j + 1]): temp = a[j] a[j] = a[j + 1] a[j + 1] = temp j = j + 1 i = i + 1 print("The Sorted List in Ascending Order : ", a)
Результат работы программы:
Please Enter the Total Number of Elements : 5 Please enter the 0 Element of List1 : 4 Please enter the 1 Element of List1 : 2 Please enter the 2 Element of List1 : 8 Please enter the 3 Element of List1 : 9 Please enter the 4 Element of List1 : 3 The Sorted List in Ascending Order : [2, 3, 4, 8, 9]
Как мы выяснили, алгоритм сортировки пузырьком действует по двойному циклу — внешнему (количество проходов) и внутреннему (по парам сравниваемых элементов). Сортировка требует (n-1) (n-1) операций, а это значит, что временная сложность алгоритма оценивается как O(n2). Метод эффективен для небольших массивов данных.
Сообщить об опечатке
Текст, который будет отправлен нашим редакторам: