AlgorithmO #14 — Сортиране по метода на мехурчето (Bubble Sort)

(Първо публикувано на 16.01.2017)

Още един алгоритъм, който илюстрира “brute force” подхода. Bubble Sort беше първият алгоритъм за сортиране (а може би и изобщо?), който научих, и се радвам, че сега имам възможността да напиша този пост за него. 😎

Нека само отново ви дам линк към един сайт с много добри обяснения за алгоритми за сортиране: Bubble Sort @ AlgoList.

Като хвърлим камък в езеро, от дъното към повърхността тръгват мехурчета, подредени по големина — най-голямото плува най-бързо, след него е следващото по-големина и т.н. Методът е наречен така, защото той подрежда елементите на масива, както се подреждат изплуващите мехурчета в езерото.

ОПИСАНИЕ:

При този алгоритъм последователно сравняваме два съседни елемента от входния списък и ги разменяме ако е необходимо. Накрая най-големият елемент “изплува” като мехурче на края на списъка. На следващата итерация изплува най-големият от останалите елементи. Повтаряме за общо n-1 итерации (n — брой елементи във входния списък).

Bubble Sort, подобно на Selection Sort, е алгоритъм, който е подходящ за малки списъци.

Сложността му е O(n²).

АЛГОРИТЪМ:

1. Сравняваме всяка двойка съседни елементи.
   Ако не са във възходящ ред, разменяме ги (ако сортираме във възходящ ред)

2. Ако сме направили поне една размяна, повтаряме стъпка 1.

—

Можем да формулираме алгоритъма и по още един начин, който ни дава по-добра представа как ще го имплементираме.

1. Сравняват се 0-ият и 1-вият елемент и се разменят, ако 0-ият е по-голям (*). Повтаряме същата процедура с 1-я елемент и 2-рия, 2-рия и 3-тия и т.н.

2. Накрая се сравняват предпоследният и последният елемент
   и се разменят, ако предпоследният е по-голям.

3. След обхождането на масива — най-големият елемент отива в края на масива.
   Повтаря се процеса, но този път се обхожда до предпоследния елемент (и след всяко обхождане се намалява границата за обхождане, докато останат 2 елемента).

(*) За сортиране във възходящ ред. Ако искаме да сортираме в низходящ ред, просто разменяме когато следващият елемент е по-малък (а не по-голям) от предишния.

ПРИМЕР:

Нека сортираме следната последователност от числа (във възходящ ред):

44, 55, 12, 42, 94, 18

Ако представим последователността като масив, в началото той ще изглежда така:

Нека милионите сравнения започнат! 😅

Обхождане 1

Започваме с елемент 0 и 1. Тъй като 44 < 55 (елемент 0 има по-малка стойност от елемент 1 и сортираме във възходящ ред), няма да разменяме нищо. Масивът запазва подредбата си и изглежда така:

Продължаваме с елемент 1 и 2. Тук виждаме, че елемент 1 (55) е по-голям от 2 (12), т.е. 55 > 12. Разменяме ги:

Продължаваме с елемент 2 и 3 (55 и 42). Тъй като 55 > 42, разменяме двете стойности:

Продължаваме с елемент 3 и 4. Тъй като 55 < 94, не разменяме нищо:

Продължаваме с елемент 4 и 5. Тъй като 94 > 18, разменяме двата елемента:

Приключихме с първото обхождане! Както се вижда, най-големият елемент в масива отиде на последно място.

Обхождане 2

Сега масивът изглежда така:

Следващото обхождане ще продължи до елемент 4.

Започваме с елемент 0 и 1. Тъй като 44 > 12, разменяме ги:

Продължаваме с елемент 1 и 2. Тъй като 44 > 42, разменяме ги:

Продължаваме с елемент 2 и 3. Тъй като 44 < 55, не разменяме нищо:

Продължаваме с елемент 3 и 4. Тъй като 55 > 18, разменяме ги:

Приключихме и с тази итерация! 😛 Отново най-големият елемент отиде на последно място.

Обхождане 3

Сега масивът изглежда така:

Следващото обхождане ще продължи до елемент 3.

Започваме с елемент 0 и 1. Тъй като 12 < 42, не разменяме нищо:

Продължаваме с елемент 1 и 2. Тъй като 42 < 44, не разменяме нищо:

Завършваме с елемент 2 и 3. Тъй като 44 > 18, разменяме ги:

Вече схванахте идеята… 😅

Обхождане 4

Сега масивът изглежда така:

Следващото обхождане ще продължи до елемент 2.

Започваме с елемент 0 и 1. Тъй като 12 < 42, не разменяме нищо:

Завършваме с елемент 1 и 2. Тъй като 42 > 18, разменяме ги:

Оказва се, че вече масивът ни е сортиран. Но алгоритъмът ще продължи с още едно обхождане (това е недостатък на Bubble Sort) до елемент 1.

За да избегнем такива излишни обхождания, в имплементацията по-долу ще използваме променлива, която помни дали сме извършили някаква размяна на предишното обхождане. Ако не сме — няма смисъл да продължаваме (масивът вече е сортиран). 😀

ИМПЛЕМЕНТАЦИЯ (Java):

—

Това е за днес! Ако видите някоя неточност, tell me. 😅