(Първо публикувано на 20.01.2017)

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

Това е Quicksort!

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

ОПИСАНИЕ:

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

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

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

АЛГОРИТЪМ:

1. Избираме “осов” елемент (нека го означим с P от “pivot”)

2. елементът с индекс (L+R) / 2 (където L е първият валиден индекс от масива, а R последният) (*)

3. Подреждаме и разделяме масива по следния начин (**):

4. всички елементи по-малки от P отиват в лявата част на масива (преди P)

5. всички елементи по-големи от P отиват в дясната част на масива (след P)

6. всички елементи равни на P могат да останат или в лявата, или в дясната част на масива

7. Сортираме двете разделени части

8. прилагаме стъпка 1 и 2 за лявата част

9. прилагаме стъпка 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:

5. разменяме стойностите на arr[i] и arr[j]

6. увеличаваме стойността на i с 1

7. намаляваме стойността на j с 1

8. Ако i > j, алгоритъмът за подреждане приключва,

9. иначе повтаряме стъпки 2, 3 и 4

След подреждането на масива:

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

ПРИМЕР:

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

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

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

Нека означим елементите с цветове, за да е по-прегледно:

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

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

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

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

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

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

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

Сега:

• разменяме стойностите на arr[i] и arrj
• увеличаваме i с 1
• намаляваме j с 1

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

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

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

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

Този път имаме късмет, защото 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)

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

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

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

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

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

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

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

Сега трябва да повторим всичко това, но за 2-та подмасива, които се образуват:

[1, 2, 5, 7, 3]
[14, 7, 26, 12]

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

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

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

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

—

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