Теория 08/06/2021 16:14

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(n²). Метод эффективен для небольших массивов данных.