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. След като намерим този елемент, започваме да намаляваме стойността на 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):

---

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