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

Още един алгоритъм, който илюстрира "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

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

Индекс	0	1	2	3	4	5
Стойност	44	55	12	42	94	18

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

---

Обхождане 1

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

Индекс	0	1	2	3	4	5
Стойност	44	55	12	42	94	18

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

Индекс	0	1	2	3	4	5
Стойност	44	12	55	42	94	18

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

Индекс	0	1	2	3	4	5
Стойност	44	12	42	55	94	18

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

Индекс	0	1	2	3	4	5
Стойност	44	12	42	55	94	18

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

Индекс	0	1	2	3	4	5
Стойност	44	12	42	55	18	94

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

---

Обхождане 2

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

Индекс	0	1	2	3	4	5
Стойност	44	12	42	55	18	94

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

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

Индекс	0	1	2	3	4	5
Стойност	12	44	42	55	18	94

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	55	18	94

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	55	18	94

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	18	55	94

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

---

Обхождане 3

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	18	55	94

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

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	18	55	94

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

Индекс	0	1	2	3	4	5
Стойност	12	42	44	18	55	94

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

Индекс	0	1	2	3	4	5
Стойност	12	42	18	44	55	94

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

---

Обхождане 4

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

Индекс	0	1	2	3	4	5
Стойност	12	42	18	44	55	94

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

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

Индекс	0	1	2	3	4	5
Стойност	12	42	18	44	55	94

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

Индекс	0	1	2	3	4	5
Стойност	12	18	42	44	55	94

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

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

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



---

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