Днешният алгоритъм е доста интересен и всъщност доста ме плашеше преди време. 😀 Това е един от най-популярните алгоритми за сортиране и е широко използван в практиката, тъй като е подходящ за големи списъци от данни.
Това е
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 -> сортирана част
Десен подмасив
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):
---
Това е за днес! Този пост ме поизмъчи повечко, но ако видите някоя неточност - свиркайте! 😀
