AlgorithmO #15 - Двоично търсене (Binary Search)

Днешният алгоритъм е изключително прост и спада към една по-различна категория алгoритми, която се нарича "разделяй и владей" (divide and conquer).

Идеята тук е, че разделяме една сложна задача на няколко по-прости, решаваме всяка една от тези по-малки задачи и накрая обединяваме решението в едно цяло.

Двоичното търсене е елементарен пример за такъв вид алгоритъм.

Трябва да кажа, че този подход е феноменален дори и извън програмирането. Аз лично го използвам почти винаги когато имам някаква тежка задача за вършене, но не искам да започна. 😃

---

ОПИСАНИЕ:

Този алгоритъм се използва за намиране на даден елемент в сортиран списък от елементи.

Двоичното търсене всъщност няма нищо общо с двоичната бройна система.

Идеята зад този алгоритъм е, че, тъй като входният ни списък е сортиран, няма нужда да сравняваме търсения елемент с всеки друг от списъка. Вместо това, можем да го сравним с елемента по средата и по този начин да разберем в коя част на масива се намира.

По този начин намаляваме значително времето за изпълнение, тъй като ограничаваме областта, в която ще търсим елемента.

Сложността му (в най-лошия случай) е O(log n), затова понякога се нарича и "логаритмично търсене".


АЛГОРИТЪМ:

1. Сравни търсения елемент с елемента по средата. *
    Ако са равни, алгоритъмът приключва.

2. Ако НЕ СА равни:
       - Ако търсеният елемент е по-малък от елемента по средата:
            - повтори стъпка 1 за подмасива преди средния елемент.
       - Ако търсеният елемент е по-голям от елемента по средата:
            - повтори стъпка 1 за подмасива след средния елемент.
   
* Елементът с индекс (L+R) / 2 (целочислено деление), където L е първият валиден индекс от масива, а R e последният валиден индекс. Без значение е дали масивът е с четен или нечетен брой елементи.

ПРИМЕР:

Нека намерим елемента със стойност 6 в следния масив:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

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

Първо трябва да определим средния елемент. Това е елементът с индекс (L+R) / 2. Тъй кaто първият валиден индекс е 0 (L = 0) и последният 9 (R = 9), индексът на средния елемент ще е (0+9) / 2 или, иначе казано, елементът с индекс 4 (не забравяйте, че взимаме цялата част от делението).

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Виждаме, че този елемент има стойност 19 и 19 > 6 (търсения елемент), затова ще повторим процедурата за подмасива започващ от елемент 0 до 3 (очевидно няма да включим елемент 4, тъй като току що определихме, че е по-голям от търсения елемент):

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Новите граници сега са L = 0 и R = 3. От това следва, че средният елемент ще има индекс (L+R) / 2, т.е. това е елементът с индекс 1.

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Тъй като 5 < 6, този път отиваме надясно в подмасива състоящ се от елемент 2 до елемент 3:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Сега границите са L = 2 и R = 3. Средният елемент е този с индекс 2:

Индекс	0	1	2	3	4	5	6	7	8	9
Стойност	-1	5	6	18	19	25	46	78	102	114

Супер! Виждаме, че средният елемент съвпада с елемента, който търсим. Открихме, че той има индекс 2 в масива.

Приключваме и се самопотупваме по рамото за добре свършена работа. 😀

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


---

Това е за днес! Ако видите някоя грешка, кажете ми и реакцията ми ще е нещо като това. 😅

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. 😅