30 януари 2017 г.

AlgorithmO #19 - Търсене на символни низове (наивен подход)

Днес ще ви покажа един прост алгоритъм за намиране на символен низ (последователност от символи) в друг символен низ.

Сигурно ви е минавало през ума, че има някаква магия, която се случва когато използвате методи като contains() или indexOf() в Java при работа със String обекти (примерно).

Нека да видим как става! 😀


---



ОПИСАНИЕ:

Този алгоритъм спада към "brute force" категорията, защото при него последователно преглеждаме всеки един символ от символен низ, докато не намерим съвпадение с търсения от нас "подниз" (substring).

29 януари 2017 г.

AlgorithmO #18 - Обхождане на двоични дървета

Днес ще се позанимаваме с нещо малко по-различно - обхождане на двоични дървета.

Няма да се спирам върху обяснения на това какво е двоично дърво - в книгата на Светлин Наков е обяснено прекрасно. Там е обяснена цялата терминология, която може да срещнете в този пост.

Тъй като последните няколко поста бяха за алгоритми от категорията "разделяй и владей", може да се учудите, но и този спада към тях. Причината е, че двоичното дървото като структура включва корен, ляво поддърво и дясно поддърво (т.е. частта "разделяй" е в самата й дефиниция). Това подсказва, че обработката на такива дървета ще използва именно подхода "разделяй и владей".

Нека да видим за какво иде реч. 😀

---

Трудно беше да избера картинка за този пост, но тази е непобедима... :)


ОПИСАНИЕ:

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

23 януари 2017 г.

AlgorithmO #17 - Сортиране чрез сливане (Merge sort)

Днес ще ви покажа още един интересен алгоритъм за сортиране, който се нарича "Merge sort". Подобно на Quicksort, и този алгоритъм спада към категорията алгоритми "разделяй и владей" и е един от най-популярните и широко използваните.

Отново алгоритъм, който на пръв поглед изглежда страшен, но всъщност само трябва да го приложите няколко пъти, за да видите, че това е просто заблуда. 😉 По-трудната част тук е имплементацията на алгоритъма.

---


ОПИСАНИЕ:

Както казахме, това е един от най-популярните алгоритми за сортиране, със сложност (в най-лошия случай) O(n log n), правейки го подходящ за списъци с голям брой елементи (и неподходящ за списъци с малък брой елементи).

Идеята зад Mergesort лесно ще ни даде обяснението защо алгоритъмът е в категорията "разделяй и владей".

20 януари 2017 г.

AlgorithmO #16 - Бързо сортиране (Quicksort)

Днешният алгоритъм е доста интересен и всъщност доста ме плашеше преди време. 😀 Това е един от най-популярните алгоритми за сортиране и е широко използван в практиката, тъй като е подходящ за големи списъци от данни.

Това е Quicksort!

Погледнете обяснението за QuickSort в AlgoList - голяма част от информацията в този пост е взета от там (страхотен сайт с много добри обяснения за редица популярни алгоритми).

---



ОПИСАНИЕ:

Quicksort е алгоритъм за сортиране от тип "разделяй и владей" (разделяме задачата за сортиране на по-малки и накрая обединяваме малките решения в едно голямо).

Както казахме, Quicksort е най-подходящ когато искаме да сортираме големи списъци от данни.

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

АЛГОРИТЪМ:

1. Избираме "осов" елемент (нека го означим с P от "pivot")
- елементът с индекс (L+R) / 2 (където L е първият валиден индекс от масива, а R последният) *

2. Подреждаме и разделяме масива по следния начин **:
-  всички елементи по-малки от P отиват в лявата част на масива (преди P)
-  всички елементи по-големи от P отиват в дясната част на масива (след P)
-  всички елементи равни на P могат да останат или в лявата, или в дясната част на масива

3. Сортираме двете разделени части
- прилагаме стъпка 1 и 2 за лявата част
- прилагаме стъпка 1 и 2 за дясната част

* Елементът може да бъде и всеки друг от масива, но по-удобно е да е някъде по средата.
** Не е задължително частите на разделения масив да са с еднакъв брой елементи.

Как става подреждането и разделянето?

1. Имаме 2 брояча - i и j.
   В началото i сочи към първия елемент на масива (или подмасива),
   a j към последния елемент.

2. Започваме да увеличаваме стойността на i с 1
  докато не намерим елемент със стойност по-голяма или равна на P (arr[i] >= P)

3. След като намерим този елемент, започваме да намаляваме стойността на с 1
  докато не намерим елемент със стойност по-малка или равна на P (arr[j] <= P)

4. Ако i <= j:
- разменяме стойностите на arr[i] и arr[j]
- увеличаваме стойността на i с 1
- намаляваме стойността на j с 1

5. Ако i > j, алгоритъмът за подреждане приключва,
- иначе повтаряме стъпки 2, 3 и 4

След подреждането на масива:
- всички елементи преди arr[i] ще са със стойност по-малка или равна на P
- всички елементи след arr[j] ще са със стойност по-голяма или равна на P.

ПРИМЕР:

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

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
12
5
26
7
14
3
7
2


Първата ни работа е да определим осов елемент! Тъй като казахме, че това ще е елемент с индекс (L+R) / 2, а в случая L = 0 и R = 8, това ще е елементът с индекс 4 (и стойност 7), т.е. P = 7.

Сега идва интересната част - подреждането и разделянето на масива.

Нека означим елементите с цветове, за да е по-прегледно:
- със син цвят ще бъде оцветен осовият елемент P
- с червен цвят ще бъде оцветен елементът, който стои на позиция i
- със зелен цвят ще бъде оцветен елементът, който стои на позиция j

В началото i = 0 (индекс на първия елемент), a j = 8 (индекс на последния елемент)

Масивът ще изглежда така:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
12
5
26
7
14
3
7
2


Сега ще увеличваме i докато не намерим елемент, за който е вярно, че arr[i] >= 7. Тъй като 1 < 7, увеличаваме стойността на i с единица:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
12
5
26
7
14
3
7
2


Този път arr[i] = 12 и е вярно, че arr[i] >= 7. Спираме да увеличаваме i.

Сега, обаче, започваме да намаляваме стойността на j, докато не намерим елемент, за който е вярно, че arr[j] <= 7.

Преди самото намаляване на стойността, проверяваме дали текущият елемент не отговаря на това условие. Оказва се, че елементът отговаря на условието (j = 8, а arr[j] = 2 и е вярно, че arr[j] <= 7).

Сега:
- разменяме стойностите на arr[i] и arr[j] (ще отбележим разменените стойности с удебелен шрифт)
- увеличаваме i с 1
- намаляваме j с 1

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

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
5
26
7
14
3
7
12


Тък като сега i = 2, j = 7 и все още е вярно, че i <= j, повтаряме алгоритъма за размяна на елементи.

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

Така, продължаваме напред! Започваме увеличаването на i докато не намерим елемент, за който е вярно, че arr[i] >= 7. Първо проверяваме дали arr[i] в момента (i = 2, arr[i] = 5) не отговаря на условието и, за жалост, не отговаря. Увеличаваме i с единица:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
5
26
7
14
3
7
12


Този път имаме късмет, защото arr[i] >= 7 (i = 3, arr[i] = 26). Започваме намаляването на стойността на j, но първо проверяваме дали arr[j] <= 7. 

Оказва се, че условието е изпълнено (j = 7, arr[j] = 7, arr[j] <= 7), затова:
- разменяме елементите arr[i] и arr[j]
- i++ (намаляваме стойността на i с 1)
- j-- (намаляваме стойността на j с 1)

Масивът ще изглежда така:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
5
7
7
14
3
26
12


i = 4 и j = 6. Следва, че i <= j, затова повтаряме познатата до болка процедура.

Преди да започнем с увеличаването на i, виждаме, че стойността на arr[i] е равна на осовия елемент, следователно направо преминаваме към намаляването на j. 

Още една добра новина - няма да се налага да намаляваме и j, защото j = 6, arr[j] = 3 и arr[j] <= 7.

Направо:
- разменяме arr[i] и arr[j]
- i++
- j--

Масивът ще изглежда така:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
5
7
3
14
7
26
12


Стигнахме до интересна ситуация. Сега i = j. Какво правим сега? Абсолютно същото като преди. 

По алгоритъм търсим елемент, за който arr[i] >= P (P = 7) и ако е нужно, увеличаваме стойността на i. Виждаме, че в момента arr[i] отговаря на това условие и затова няма да увеличаваме i.

След това проверяваме дали arr[j] <= P и ако не, намаляваме стойността на j с 1 докато не намерим отговарящ на условието елемент. В момента arr[j] > 7, следователно намаляваме j с 1:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
5
7
3
14
7
26
12


Най-накрая! i > j! Това означава, че приключихме... с 2-рата стъпка от QuickSort алгоритъма! 😅

Сега трябва да повторим всичко това, но за 2-та подмасива, които се образуват:
- [1, 2, 5, 7, 3]
- [14, 7, 26, 12]

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

---

Ляв подмасив
1) 1, 2, 5, 7, 3
P = 5
1, 2, 5, 7 3
1, 2, 5, 7, 3
1, 2, 3, 7, 5
1, 2, 37, 5
---
1.1) 1, 2, 3 -> сортирана част
---
1.2) 7, 5
P = 7
7, 5
5, 7
---
1.2.1) 5 -> сортирана част
1.2.2) 7 -> сортирана част


Десен подмасив
2) 14, 7, 26, 12
P = 7
14, 7, 26, 12
14, 7, 26, 12
7, 14, 26, 12
---
2.1) 7 -> сортирана част
---
2.2) 14, 26, 12
P = 26
14, 26, 12
14, 26, 12
14, 12, 26
---
2.1) 14, 12
P = 14
14, 12
12, 14
---
2.2.1) 12 -> сортирана част
2.2.2) 14 -> сортирана част
---
2.2) 26 -> сортирана част


* Забележка: Quicksort в някои случаи ще навлезе дори още по-дълбоко в рекурсията. Тук спестявам тези допълнителни извиквания, които се правят след като даденият подмасив (или подподмасив 😁) вече е сортиран.

Накрая просто обединяваме сортираните части (започвайки от левия подмасив) и получаваме сортирания масив:

Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
3
5
7
7
12
14
26


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

---

Това е за днес! Този пост ме поизмъчи повечко, но ако видите някоя неточност - свиркайте! 😀

18 януари 2017 г.

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):


---

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