Bubblе Алгоритм сортування с Python використовуючи приклад списку

Що таке? Bubble Сортувати?

Bubble Сортування це алгоритм сортування, який використовується для сортування елементів списку в порядку зростання шляхом порівняння двох суміжних значень. Якщо перше значення вище за друге значення, перше значення займає друге значення, тоді як друге значення займає перше значення. Якщо перше значення менше, ніж друге значення, то заміна не виконується.

Цей процес повторюється, доки всі значення в списку не будуть порівняні та замінені місцями, якщо необхідно. Кожну ітерацію зазвичай називають проходом. Кількість проходів у бульбашковому сортуванні дорівнює кількості елементів у списку мінус один.

В цьому Bubble Сортування в Python підручник ти навчишся:

Впровадження Bubble Алгоритм сортування

Ми розіб’ємо реалізацію на три (3) кроки, а саме проблему, рішення та алгоритм, який ми можемо використовувати для написання коду для будь-якої мови.

Проблема

Список предметів подано у довільному порядку, і ми хотіли б розташувати елементи впорядковано

Розглянемо наступний список:

[21,6,9,33,3]

Рішення

Переглядайте список, порівнюючи два суміжні елементи та міняючи їх місцями, якщо перше значення вище за друге.

Результат повинен бути таким:

[3,6,9,21,33]

Алгоритм

Алгоритм бульбашкового сортування працює наступним чином

Крок 1) Отримайте загальну кількість елементів. Отримайте загальну кількість елементів у наданому списку

Крок 2) Визначте кількість зовнішніх проходів (n – 1), які необхідно виконати. Його довжина дорівнює списку мінус один

Крок 3) Виконайте внутрішні проходи (n – 1) разів для зовнішнього проходу 1. Отримайте значення першого елемента та порівняйте його з другим значенням. Якщо друге значення менше першого, поміняйте місцями місцями

Крок 4) Повторіть крок 3 проходу, доки не досягнете зовнішнього проходу (n – 1). Отримайте наступний елемент у списку, а потім повторіть процес, який було виконано на кроці 3, доки всі значення не будуть розміщені в правильному порядку зростання.

Крок 5) Поверніть результат, коли всі проходи будуть зроблені. Повернути результати відсортованого списку

Крок 6) Алгоритм оптимізації

Уникайте непотрібних внутрішніх проходів, якщо список або суміжні значення вже відсортовано. Наприклад, якщо наданий список уже містить елементи, які були відсортовані в порядку зростання, тоді ми можемо розірвати цикл раніше.

Оптимізований Bubble Алгоритм сортування

За замовчуванням використовується алгоритм бульбашкового сортування Python порівнює всі елементи в списку незалежно від того, чи список уже відсортовано чи ні. Якщо заданий список уже відсортовано, порівняння всіх значень є марною тратою часу та ресурсів.

Оптимізація бульбашкового сортування допомагає нам уникнути непотрібних ітерацій і заощадити час і ресурси.

Наприклад, якщо перший і другий елементи вже відсортовано, то немає потреби переглядати решту значень. Ітерація припиняється, і починається наступна, доки процес не завершиться, як показано нижче Bubble Приклад сортування.

Оптимізація виконується за допомогою наступних кроків

Крок 1) Створіть змінну-прапорець, яка відстежуватиме, чи відбулася якась заміна у внутрішньому циклі

Крок 2) Якщо значення помінялися місцями, перейдіть до наступної ітерації

Крок 3) Якщо переваги не помінялися місцями, припиніть внутрішній цикл і продовжте зовнішній цикл.

Оптимізоване бульбашкове сортування ефективніше, оскільки воно виконує лише необхідні кроки та пропускає непотрібні.

Візуальне уявлення

З огляду на список із п’яти елементів, наступні зображення ілюструють, як спливаюче сортування повторює значення під час сортування

На наступному зображенні показано несортований список

Перша ітерація

Крок 1)

Значення 21 і 6 порівнюються, щоб перевірити, яке з них більше за інше.

21 більше за 6, тому 21 займає позицію, яку займає 6, а 6 займає позицію, яку займає 21

Наш змінений список тепер виглядає як наведений вище.

Крок 2)

Значення 21 і 9 порівнюються.

21 більше за 9, тому ми міняємо місцями 21 і 9

Новий список тепер такий, як і вище

Крок 3)

Значення 21 і 33 порівнюються, щоб знайти більше.

Значення 33 більше за 21, тому заміна не відбувається.

Крок 4)

Значення 33 і 3 порівнюються, щоб знайти більше.

Значення 33 більше за 3, тому ми міняємо їх місцями.

Відсортований список у кінці першої ітерації схожий на наведений вище

Друга ітерація

Новий список після другої ітерації виглядає наступним чином

Третя ітерація

Новий список після третьої ітерації виглядає наступним чином

Четверта ітерація

Новий список після четвертої ітерації виглядає наступним чином

Python прикладів

Наступний код показує, як реалізувати Bubble Алгоритм сортування в Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Виконання наведеної вище програми бульбашкового сортування в Python дає наступні результати

[6, 9, 21, 3, 33]

Пояснення коду

Пояснення до Python Bubble Програмний код сортування виглядає наступним чином

ТУТ,

Визначає функцію bubbleSort, яка приймає параметр theSeq. Код нічого не виводить.
Отримує довжину масиву та присвоює значення змінній n. Код нічого не виводить
Запускає цикл for, який запускає алгоритм бульбашкового сортування (n – 1) разів. Це зовнішня петля. Код нічого не виводить
Визначає змінну-прапорець, яка використовуватиметься для визначення того, відбулася заміна чи ні. Це з метою оптимізації. Код нічого не виводить
Запускає внутрішній цикл, який порівнює всі значення в списку від першого до останнього. Код нічого не виводить.
Використовує оператор if, щоб перевірити, чи значення в лівій частині більше, ніж у безпосередній правій частині. Код нічого не виводить.
Призначає значення theSeq[j] часовій змінній tmp, якщо умова оцінюється як істинна. Код нічого не виводить
Значення theSeq[j + 1] присвоюється позиції theSeq[j]. Код нічого не виводить
Значення змінної tmp присвоюється позиції theSeq[j + 1]. Код нічого не виводить
Змінній flag присвоюється значення 1, щоб вказати, що відбувся обмін. Код нічого не виводить
Використовує оператор if, щоб перевірити, чи значення прапора змінної дорівнює 0. Код нічого не виводить
Якщо значення дорівнює 0, ми викликаємо оператор break, який виходить із внутрішнього циклу.
Повертає значення theSeq після його сортування. Код виводить відсортований список.
Визначає змінну el, яка містить список випадкових чисел. Код нічого не виводить.
Призначає значення функції bubbleSort змінній result.
Виводить значення змінної результат.

Bubblпереваги сортування

Нижче наведено деякі з переваг алгоритму бульбашкового сортування

Це легко зрозуміти
Він працює дуже добре, коли список уже або майже відсортований
Він не вимагає великої пам'яті.
Написати код для алгоритму легко
Вимоги до простору мінімальні порівняно з іншими алгоритмами сортування.

Bubble sort Недоліки

Нижче наведено деякі з недоліків алгоритму бульбашкового сортування

Він погано працює під час сортування великих списків. Це займає надто багато часу та ресурсів.
Здебільшого він використовується в академічних цілях, а не в реальних програмах.
Кількість кроків, необхідних для сортування списку, має порядок n²

Аналіз складності Bubble Сортування

Існує три типи складності:

1) Складність сортування

Складність сортування використовується для вираження кількості часу виконання та місця, необхідного для сортування списку. Бульбашкове сортування виконує (n – 1) ітерацій для сортування списку, де n – загальна кількість елементів у списку.

2) Часова складність

Часова складність бульбашкового сортування дорівнює O(n²)

Часові складності можна класифікувати як:

Найгірший випадок – тут представлений список у порядку спадання. Алгоритм виконує максимальну кількість виконань, яка виражається як [Big-O] O(n²)
Найкращий випадок – це відбувається, коли наданий список уже відсортовано. Алгоритм виконує мінімальну кількість виконань, яка виражається як [Big-Omega] Ω(n)
Середній випадок – це відбувається, коли список у довільному порядку. Середня складність представлена як [велика тета] ⊝(n²)

3) Просторова складність

Складність простору вимірює кількість додаткового простору, необхідного для сортування списку. Бульбашкове сортування вимагає лише одного (1) додаткового місця для тимчасової змінної, яка використовується для заміни значень. Тому він має просторову складність O (1).

Підсумки

Алгоритм бульбашкового сортування працює шляхом порівняння двох суміжних значень і заміни їх місцями, якщо значення ліворуч менше значення справа.
Реалізація алгоритму бульбашкового сортування відносно проста Python. Все, що вам потрібно використовувати, це цикли for і оператори if.
Проблема, яку вирішує алгоритм бульбашкового сортування, полягає в тому, щоб отримати випадковий список елементів і перетворити його на впорядкований список.
Алгоритм бульбашкового сортування в структурі даних працює найкраще, коли список уже відсортовано, оскільки він виконує мінімальну кількість ітерацій.
Алгоритм бульбашкового сортування не працює добре, якщо список розташовано у зворотному порядку.
Сортування барботером має часову складність O (n²) і просторову складність O (1)
Алгоритм барботерського сортування найкраще підходить для академічних цілей, а не для реальних програм.
Оптимізоване бульбашкове сортування робить алгоритм більш ефективним, пропускаючи непотрібні ітерації під час перевірки значень, які вже були відсортовані.

Вам може сподобатися: