Днес ще ви покажа един прост алгоритъм за намиране на символен низ (последователност от символи) в друг символен низ.
Сигурно ви е минавало през ума, че има някаква магия, която се случва когато използвате методи като contains() или indexOf() в Java при работа със String обекти (примерно).
Нека да видим как става! 😀
---
ОПИСАНИЕ:
Този алгоритъм спада към "brute force" категорията, защото при него последователно преглеждаме всеки един символ от символен низ, докато не намерим съвпадение с търсения от нас "подниз" (substring).
Днес ще се позанимаваме с нещо малко по-различно - обхождане на двоични дървета.
Няма да се спирам върху обяснения на това какво е двоично дърво - в книгата на Светлин Наков е обяснено прекрасно. Там е обяснена цялата терминология, която може да срещнете в този пост.
Тъй като последните няколко поста бяха за алгоритми от категорията "разделяй и владей", може да се учудите, но и този спада към тях. Причината е, че двоичното дървото като структура включва корен, ляво поддърво и дясно поддърво (т.е. частта "разделяй" е в самата й дефиниция). Това подсказва, че обработката на такива дървета ще използва именно подхода "разделяй и владей".
Нека да видим за какво иде реч. 😀
---
Трудно беше да избера картинка за този пост, но тази е непобедима... :)
ОПИСАНИЕ: "Обхождане" означава да преминем през всеки един елемент на дадена структура. В структури като стек, опашка. свързан списък и т.н. има само един логически път, по който можем да направим това обхождане.
Днес ще ви покажа още един интересен алгоритъм за сортиране, който се нарича "Merge sort". Подобно на Quicksort, и този алгоритъм спада към категорията алгоритми "разделяй и владей" и е един от най-популярните и широко използваните.
Отново алгоритъм, който на пръв поглед изглежда страшен, но всъщност само трябва да го приложите няколко пъти, за да видите, че това е просто заблуда. 😉 По-трудната част тук е имплементацията на алгоритъма.
---
ОПИСАНИЕ:
Както казахме, това е един от най-популярните алгоритми за сортиране, със сложност (в най-лошия случай) O(n log n), правейки го подходящ за списъци с голям брой елементи (и неподходящ за списъци с малък брой елементи).
Идеята зад Mergesort лесно ще ни даде обяснението защо алгоритъмът е в категорията "разделяй и владей".
Днешният алгоритъм е доста интересен и всъщност доста ме плашеше преди време. 😀 Това е един от най-популярните алгоритми за сортиране и е широко използван в практиката, тъй като е подходящ за големи списъци от данни.
Това е 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. След като намерим този елемент, започваме да намаляваме стойността на j с 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, 3, 7, 5 --- 1.1) 1, 2, 3 -> сортирана част
--- 1.2) 7, 5 P = 7 7, 5 5, 7
---
1.2.1) 5 -> сортирана част
1.2.2) 7 -> сортирана част
* Забележка: Quicksort в някои случаи ще навлезе дори още по-дълбоко в рекурсията. Тук спестявам тези допълнителни извиквания, които се правят след като даденият подмасив (или подподмасив 😁) вече е сортиран.
Накрая просто обединяваме сортираните части (започвайки от левия подмасив) и получаваме сортирания масив:
Индекс
0
1
2
3
4
5
6
7
8
Стойност
1
2
3
5
7
7
12
14
26
ИМПЛЕМЕНТАЦИЯ (Java):
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Днешният алгоритъм е изключително прост и спада към една по-различна категория алг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):
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
