Перегляд вихідного коду сторінки Сортування бульбашкою

{{Картка_алгоритм
|клас=[[Алгоритм сортування]]
|зображення=[[Файл:Bubble_sort_animation.gif]]
|дані=[[Масив (структура даних)|Масив]]
|час=''О(n²)''
|найкращий час=''О(n)''
|середній час=''О(n²)''
|простір=''О(n)'' загальний, ''O(1)'' допоміжний 
|оптимальний=Ні
}}
[[File:Bubblesort-edited-color.svg|міні|300px|alt=Статична візуалізація сортування бульбашкою|Статична візуалізація сортування бульбашкою]]
[[File:Bubble-sort-example-300px.gif|alt=Анімація, що показує приклад роботи алгоритму.|thumb|Наочна демонстрація алгоритму.]]

'''Сортування обміном''' або '''сортування бульбашкою'''&nbsp;— це простий [[алгоритм сортування]].

== Принцип роботи ==
Алгоритм працює таким чином&nbsp;— у поданому наборі даних (списку чи масиві) порівнюються два сусідні елементи. Якщо один з елементів не відповідає критерію сортування (є більшим, або ж, навпаки, меншим за свого сусіда), то ці два елементи [[Обмін (інформатика)|міняються місцями]]. Прохід по списку продовжується доти, доки дані не будуть відсортованими. Алгоритм отримав свою назву від того, що процес сортування за ним нагадує поведінку бульбашок повітря у резервуарі з водою. Оскільки для роботи з елементами масиву він використовує лише порівняння, це [[сортування на основі порівнянь]].

== Аналіз ==

=== Продуктивність ===
Складність алгоритму у найгіршому випадку рівна ''[[Нотація Ландау|О]]''(''n''²), де ''n''&nbsp;— кількість елементів для сортування. Існує чимало значно ефективніших алгоритмів, наприклад, з найгіршою ефективністю рівною ''O''(''n'' log ''n''). Тому даний алгоритм має низьку ефективність у випадках, коли N є досить великим, за винятком рідкісних конкретних випадків, коли заздалегідь відомо, що масив з самого початку буде добре відсортований.

=== Кролики і черепахи ===
Позиції елементів, що підлягають сортуванню відіграють велику роль у питанні продуктивності даного алгоритму. Великі елементи на початку списку не являють проблему, оскільки вони досить швидко зміщуються на свої місця. Однак, малі елементи у кінці списку переміщуються на його початок дуже повільно. Це призвело до того, що обидва типи елементів було названо [[кріль|кролями]] і [[черепаха]]ми, відповідно.

З метою підвищення швидкодії алгоритму, у свій час було здійснено чимало зусиль для зменшення кількості «черепах». [[Сортування перемішуванням]] є порівняно непоганим, однак, усе ще у своєму найгіршому випадку має складність ''O(n<sup>2</sup>)''. [[Сортування гребінцем]] спершу порівнює великі елементи один з одним, а вже тоді поступово переходить до все менших і менших. Його середньостатистична швидкість приблизно рівна такій в алгоритмі [[Швидке сортування]].

=== Приклад реалізації крок за кроком ===
Візьмемо масив чисел «5 1 4 2 8», і за допомогою даного алгоритму, відсортуємо його від найменшого до найбільшого елементу. На кожному кроці, елементи, виділені '''жирним''' шрифтом будуть порівнюватись.

'''Перший прохід:'''<br/>
('''5''' '''1''' 4 2 8) <math>\to</math> ('''1''' '''5''' 4 2 8) Тут, алгоритм порівнює перші два елементи, і міняє їх місцями.<br/>
(1 '''5''' '''4''' 2 8) <math>\to</math> (1 '''4''' '''5''' 2 8)<br/>
(1 4 '''5''' '''2''' 8) <math>\to</math> (1 4 '''2''' '''5''' 8)<br/>
(1 4 2 '''5''' '''8''') <math>\to</math> (1 4 2 '''5''' '''8''') Тут порівнювані елементи знаходяться на своїх місцях, тож алгоритм не міняє їх місцями.

Після першого проходу масиву найбільший елемент гарантовано опинився на останній позиції, тому в подальшому можна виключити його з роботи.<br/>
'''Другий прохід:'''<br/>
('''1''' '''4''' 2 5 8) <math>\to</math> ('''1''' '''4''' 2 5 8)<br/>
(1 '''4''' '''2''' 5 8) <math>\to</math> (1 '''2''' '''4''' 5 8)<br/>
(1 2 '''4''' '''5''' 8) <math>\to</math> (1 2 '''4''' '''5''' 8) Після другого проходу два найбільших елементи масиву гарантовано опинилися на своїх позиціях, тому в подальшому можна виключити їх з роботи.<br/>
Тепер наш масив повністю відсортований, однак, алгоритм цього ще не знає. Йому потрібен ще один «пустий» прохід, під час якого він не поміняє місцями жодного елементу.<br/>
'''Третій прохід:'''<br/>
('''1''' '''2''' 4 5 8) <math>\to</math> ('''1''' '''2''' 4 5 8)<br/>
(1 '''2''' '''4''' 5 8) <math>\to</math> (1 '''2''' '''4''' 5 8)<br/>
Нарешті, масив відсортовано, і алгоритм може припинити свою роботу.<br/>

== Реалізація ==
Алгоритм можна виразити як (масив зі стартовим індексом 0):
<syntaxhighlight lang="pli">
процедура бульбашка( A : список елементів придатних для сортування )
   повторювати     
     переставлені = хиба
     для i = 1 включно до довжина(A) - 1 робити:
       /* якщо ця двійка невпорядкована */
       якщо A[i-1] > A[i] тоді
         /* поміняти місцями і запам'ятати, що щось змінилось */
         переставити( A[i-1], A[i] )
         переставлені = істина
       кінець якщо
     кінець для
   доки не переставлені
кінець процедури
</syntaxhighlight>

== На практиці ==
Хоча алгоритм є одним із найпростіших алгоритмів сортування, його ефективність є досить низькою, і він погано підходить для сортування великих списків. Більшість інших алгоритмів з такою ж швидкодією ''O(n<sup>2</sup>)'' є ефективнішими за алгоритм сортування бульбашками, наприклад, [[сортування включенням]].

Через свою простоту алгоритм часто використовується для пояснення студентам концепції алгоритмів, зокрема алгоритмів сортування. Однак деякі дослідники, як то [[Оуен Астрахан]] (Owen Astrachan), ретельно дослідивши даний алгоритм, стверджують, що він настільки поганий і неефективний, що вони навіть не використовуватимуть його як приклад у своїй викладацькій діяльності.<ref>http://www.cs.duke.edu/~ola/papers/bubble.pdf</ref>

[[Дональд Кнут]] у своїй знаменитій праці ''[[The Art of Computer Programming]]'' прийшов до висновку, що «немає жодних підстав рекомендувати використовувати даний алгоритм, окрім хіба що через примітну назву і через те, що він є лідером у кількості цікавих теоретичних проблем», частину з яких він обговорює у своїй праці.

Сортування бульбашкою під час своєї роботи є [[Нотація Ландау|асимптоматичним]] еквівалентом алгоритму [[сортування включенням]] у своєму найгіршому випадку, однак обидва алгоритми дуже сильно відрізняються кількістю необхідних операцій переміщення. Результати низки експериментів, наприклад, проведених [[Оувен Астрахан|Астраханом]] також підтверджують той факт, що продуктивність алгоритму [[сортування включенням]] є значно вищою. Тому багато сучасних посібників з алгоритмів навіть не згадують про алгоритм сортування бульбашками і віддають перевагу [[сортування включенням|сортуванню включеннями]].

Сортування бульбашкою також погано використовує можливості сучасних [[мікропроцесор]]ів. Воно вимагає щонайменше удвічі більше операцій, ніж [[сортування включенням]], удвічі більше [[кеш]]у пам'яті, і [[Нотація Ландау|асимптоматично]] більше [[передбачувач переходів|передбачень переходів]]. Результати експериментів, проведених [[Оувен Астрахан|Астраханом]], показали, що сортування рядка за алгоритмом сортування бульбашками у п'ять разів повільніше за сортування того ж рядка за алгоритмом [[сортування включенням]] і на 40% повільніше за [[сортування вибором]].<ref>Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003. [http://www.cs.duke.edu/~ola/papers/bubble.pdf (pdf)]</ref>

== Примітки ==
{{reflist}}

== Джерела ==
* {{TAOCP.v3}}
* {{CLRS|chapter=2.2 Аналіз алгоритмів}}
* [https://www.cs.tcd.ie/publications/tech-reports/reports.05/TCD-CS-2005-57.pdf Sorting in the Presence of Branch Prediction and Caches]

== Посилання ==
* [http://www.sorting-algorithms.com/bubble-sort Animated Sorting Algorithms: Bubble Sort]&nbsp;— графічна демонстрація роботи алгоритму.
* [http://www.youtube.com/watch?v=lyZQPjUT5B4 Наочна демонстрація бульбашкового сортування угорськими танцюристами.]
* [https://web.archive.org/web/20090201185531/http://www.ndsu.nodak.edu/instruct/juell/vp/cs1and2/sortdemo/BubbleSortDemo_ny.html Bubble Sort Demo]
* [http://web.engr.oregonstate.edu/~minoura/cs261/javaProgs/sort/BubbleSort.html Bubble Sort Demonstration]
* [http://lecture.ecc.u-tokyo.ac.jp/~ueda/JavaApplet/BubbleSort.html Lafore's Bubble Sort]
* [http://www.cs.pitt.edu/~kirk/cs1501/animations/Sort3.html Sorting Applets in C++]
* [http://www.paked.net/subject_pages/computer_science/prog2.htm C++ Program&nbsp;— Bubble Sort ]
* [https://web.archive.org/web/20081011150849/http://tide4javascript.com/?s=Bubble Analyze Bubble Sort in an online Javascript IDE]
* [https://web.archive.org/web/20081207090529/http://coderaptors.com/?BubbleSort A colored graphical Java applet]

{{Algorithm-stub}}
{{Алгоритми сортування}}
{{ВП-портали|Програмування|Інформаційні технології}}

[[Категорія:Алгоритми сортування]]
[[Категорія:Статті з прикладами коду]]