Алгоритм сортування міхурів за допомогою Python на прикладі списку

Зміст:

Anonim

Що таке сортування міхурів?

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

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

У цьому підручнику з сортування бульбашок у Python ви дізнаєтесь:

  • Що таке сортування міхурів?
  • Впровадження алгоритму сортування міхурів
  • Оптимізований алгоритм сортування міхурів
  • Візуальне представлення
  • Приклади Python
  • Пояснення коду
  • Переваги сортування бульбашок
  • Недоліки сортування бульбашок
  • Аналіз складності сортування міхурів

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

Ми розберемо реалізацію на три (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) Оптимізуйте алгоритм

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

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

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

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

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

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

Крок 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

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

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

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

[6, 9, 21, 3, 33]

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

Пояснення програмного коду Python Bubble Sort таке

ТУТ,

  1. Визначає функцію bubbleSort, яка приймає параметр theSeq. Код нічого не виводить.
  2. Отримує довжину масиву та присвоює значення змінній n. Код нічого не виводить
  3. Запускає цикл for, який запускає алгоритм сортування бульбашок (n - 1) разів. Це зовнішній цикл. Код нічого не виводить
  4. Визначає змінну прапора, яка буде використовуватися для визначення того, відбулася підміна чи ні. Це для цілей оптимізації. Код нічого не виводить
  5. Запускає внутрішній цикл, який порівнює всі значення у списку від першого до останнього. Код нічого не виводить.
  6. Застосовує оператор if, щоб перевірити, чи більше значення на лівій стороні, ніж значення на безпосередній правій стороні. Код нічого не виводить.
  7. Призначає значення theSeq [j] тимчасовій змінній tmp, якщо умова має значення true. Код нічого не виводить
  8. Значення theSeq [j + 1] присвоюється позиції theSeq [j]. Код нічого не виводить
  9. Значення змінної tmp присвоюється позиції Seq [j + 1]. Код нічого не виводить
  10. Змінній прапора присвоюється значення 1, щоб вказати, що відбувся обмін. Код нічого не виводить
  11. Використовує оператор if, щоб перевірити, чи значення прапорця змінної дорівнює 0. Код нічого не виводить
  12. Якщо значення дорівнює 0, тоді ми називаємо оператор break, який виходить із внутрішнього циклу.
  13. Повертає значення theSeq після його сортування. Код виводить відсортований список.
  14. Визначає змінну el, яка містить список випадкових чисел. Код нічого не виводить.
  15. Присвоює значення функції bubbleSort змінному результату.
  16. Друкує значення змінної result.

Переваги сортування бульбашок

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

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

Недоліки сортування бульбашок

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

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

Аналіз складності сортування міхурів

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

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

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

2) Складність часу

Складність у часі сорту бульбашок становить O (n 2 )

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

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

3) Космічна складність

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

Резюме

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