Бързи Сортирания

Fast Sorting Algorithms

Алгоритми за бързо сортиране. Сложност и имплементации.
Бързо сортиране (Quicksort)
Сортиране чрез сливане (Mergesort)
Пирамидално сортиране (Heapsort)
Сортиране чрез броене (Counting sort)
Автор: Александър Георгиев

?Напомняме, че STL-ският сорт, за който говорихме в миналата тема за сортиране, също е бърз, в смисъл на O(N∙logN) алгоритъм. Той всъщност е съчетание от няколко алгоритъма. В GCC/G++ имплементацията той е Quicksort/Heapsort комбинация (Introsort), пускана до дълбочина 2*log2(N), след което бива приложен Insertion Sort.
В темата за сортиране разгледахме няколко прости алгоритъма за сортиране, които за съжаление нямат голяма практическа стойност, тъй като бяха бавни. В тази тема ще разгледаме няколко бързи алгоритъма, постигащи оптималната O(N∙log(N)) сложност за сортиране, базирано на сравнения: бързо сортиране (Quicksort), сортиране чрез сливане (Mergesort), и пирамидално сортиране (Heapsort). Допълнително ще разгледаме как вида на елементите, които искаме да сортираме, може да ни помогне да слезем под тази сложност в някои случаи.

Задача

Дадени са ни 1 ≤ N ≤ 1,000,000 цели числа {A0, A1, …, AN-1}. Преподредете ги така, че да е изпълнено Ai ≤ Ai+1 за i < N - 1.
Това е отново задачата за сортиране, но със значително по-големи ограничения. Тук бавните алгоритми за сортиране (например Bubble Sort или Insertion Sort) биха били твърде неефективни - биха отнемали по приблизително 15-20 минути за да сортират 1,000,000 числа.

Бързо сортиране (Quicksort)

?В остатъка от темата само ще споменаваме българските наименования на алгоритмите, но основно ще ползваме английските им еквиваленти, понеже тях ще срещате почти навсякъде другаде.
Може би най-популярният от O(N∙logN) алгоритмите за сортиране е Quicksort, наричано на български "бързо сортиране".

Идея

Това е рекурсивен алгоритъм, който на всяка стъпка фиксира един от подадените елементи за разделител (pivot), след което разделя числата на три части - тези по-малки от разделителя, тези равни на него, и тези по-големи от него. Ако сортираме първата част, след нея поставим втората част (без да правим нищо върху нея - тя вече е сортирана, тъй като всички елементи в нея са с равна стойност), и накрая сортираме третата част и я поставим след първата и втората, в крайна сметка всички елементи ще са сортирани.

Така стъпките на алгоритъма (при всяко викане на рекурсията) са:
  1. Избираме един от елементите за pivot.
  2. Вземаме всички елементи, по-малки от pivot (да кажем S1 на брой), сортираме ги прилагайки същия алгоритъм рекурсивно, и ги поставяме на позиции 0...S1-1 от резултатния масив.
  3. Вземаме всички елементи, равни на pivot (да кажем S2 на брой) и ги поставяме на позиции S1...S1+S2-1 от резултатния масив.
  4. Вземаме всички елементи, по-големи от pivot (да кажем S3 на брой), сортираме ги прилагайки същия алгоритъм рекурсивно, и ги поставяме на позиции S1+S2...N-1 от резултатния масив.

Имплементация

Вместо да подаваме масив (или vector) като аргумент и да връщаме сортирания му вариант, ще подаваме интервал от входния масив и ще работим в него (тъй като, ако направим имплементацията хитро, не ни трябва допълнителна памет за този алгоритъм). Това прави имплементацията значително по-бърза, а както ще видите - и кратка.
?Алтернативен начин да се имплементира подаването на част от масив би било с подаване на два индекса left и right, указващи, съответно, първия и последния индекс от интервала, който искаме да сортираме.
По-конкретно, рекурсията ще приема указател към първия елемент от масива, който искаме да сортираме, както и брой елементи от този указател нататък. В началото извикваме рекурсията с указател към първия елемент от масива и брой елементи N. Дъното на рекурсията е когато масивът има 0 или 1 елемента, тъй като те са вече сортирани.
void
quicksort(
int
*
array
,
int
size) {
if
(size
>
1
) {
int
pivot
=
array[random()
%
size]
;
// Less
int
left
=
0
;
for
(
int
i
=
0
;
i
<
size
;
i
+
+
)
if
(array[i]
<
pivot) swap(array[i]
,
array[left
+
+
])
;
quicksort(array
,
left)
;
// Greater
int
right
=
size
-
1
;
for
(
int
i
=
size
-
1
;
i
>
=
left
;
i
-
-
)
if
(pivot
<
array[i]) swap(array[i]
,
array[right
-
-
])
;
quicksort(array
+
right
+
1
,
size
-
right
-
1
)
;
} }

Няколко детайла в имплементацията:

Най-добър и най-лош случай

?На рандом тестове тази имплементация е около два пъти по-бавна от вградения в STL sort().
В най-най-добрия случай всички елементи са равни и приключваме още на първата стъпка (S1 и S3 са равни на 0). В него алгоритъмът върви за O(N).

В по-реалистичен случай, в който повечето елементи са различни, изборът на произволен pivot ще генерира следните размери на трите части:
Забележете, че така (намаляйки размера на две всеки път) постигаме дълбочина на рекурсията от приблизително O(log(N)) (докато стигнем граничните случаи от 0 или 1 елемента).

В най-лошия случай pivot ще е винаги или най-големият или най-малкият елемент, като "разделянето" няма да върши почти нищо - две от групите ще имат никакви или почти никакви елементи, докато третата ще съдържа почти всички. Така се достига сложност от O(N2), което е колкото беше и сложността на "бавните" алгоритми: Bubble Sort, Insertion Sort, и Selection Sort. Това обаче е много малко вероятно, ако ползваме хубав random. Нещо повече, ако ползваме линейния алгоритъм за намиране на медиана (и pivot-ът ни е медианата на елементите) разделянето ще е перфектно и никога няма да достигнем до този случай - при тази имплементация целият Quicksort става със сложност O(N∙log(N)).

Сортиране чрез сливане (Mergesort)

Друг много популярен "бърз" алгоритъм за сортиране е Mergesort, познат на български като "сортиране чрез сливане". Той също има гарантирана сложност O(N∙log(N)), но за разлика от Quicksort тя е такава както в най-лошия, така и в най-добрия случай дори без да се правят някакви специфични оптимизации (като например изискването за добър random при избирането на pivot-а). За сметка на това за имплементирането на този алгоритъм ни трябва O(N) допълнителна памет (вижте имплементацията по-нататък за да видите защо).

Идея

Ако имаме два сортирани масива A1 и A2, съдържащи, съответно, S1 и S2 елемента, то можем да ги обединим в един (отново сортиран) масив с S1+S2 елемента със сложност O(S[1] + S[2]). Това става като на всяка стъпка проверяваме кой от двата масива съдържа по-малък елемент на най-лявата си (все още невзета) позиция и го поставим на следваща позиция в резултатния масив.

Съответно, идеята е рекурсивно да разделяме подадения ни масив на две равни части, да сортираме всяка от тях, и после да обединяваме резултатите. Ако забелязвате, това е директно приложение на техниката Разделяй и Владей.

Имплементация

Първо ще имплементираме функция, която приема като аргумент два сортирани масива и ги обединява (или слива, откъдето идва името на алгоритъма) в трети.
void
merge(
int
*
array1
,
int
size1
,
int
*
array2
,
int
size2
,
int
*
where) {
int
idx1
=
0
,
idx2
=
0
;
while
(idx1
<
size1
&
&
idx2
<
size2) {
if
(array1[idx1]
<
array2[idx2]) where[idx1
+
idx2]
=
array1[idx1]
,
idx1
+
+
;
else
where[idx1
+
idx2]
=
array2[idx2]
,
idx2
+
+
;
}
while
(idx1
<
size1) where[idx1
+
idx2]
=
array1[idx1]
,
idx1
+
+
;
while
(idx2
<
size2) where[idx1
+
idx2]
=
array2[idx2]
,
idx2
+
+
;
}
Забележете, че няма как да извършим обединяването без да имаме някаква допълнителна памет, където да запишем резултата. Точно и затова на този алгоритъм (за разлика от Quicksort) му е нужна O(N) допълнителна памет.

След като имаме тази функция остава да имплементираме рекурсивното "цепене" на масива на две равни части, викането на същия алгоритъм върху всяка от тях, и после обединяването им (ползвайки тази функция).
void
mergeSort(
int
*
array
,
int
size
,
int
*
aux) {
if
(size
>
1
) { mergeSort(array
,
size
/
2
,
aux)
;
mergeSort(array
+
size
/
2
,
size
-
size
/
2
,
aux
+
size
/
2
)
;
merge(array
,
size
/
2
,
array
+
size
/
2
,
size
-
size
/
2
,
aux)
;
memcpy(array
,
aux
,
sizeof
(array[
0
])
*
size)
;
} }
?Знаете ли, че Мergesort може да се ползва за да се преброят инверсиите в масив (инверсия е ако за два индекса i < j имаме Ai > Aj).
Тук няма нищо необичайно - имаме дъно на рекурсия (не е нужно да сортираме по-малко от два елемента), след което рекурсивно сортираме първата и втората половина на подадения ни масив (виканията на mergeSort()), след което ги обединяваме в допълнителния масив (викането на merge()), и връщаме обратно в оригиналния (функцията memcpy()).

Най-добър и най-лош случай

?На рандом тестове тази имплементация е малко повече от два пъти по-бавна от вградения в STL sort().
Както казахме и по-рано, тук независимо от входните данни алгоритъмът винаги прави около N * log(N) операции.

Пирамидално сортиране (Heapsort)

Третият от най-популярните бързи алгоритми за сортиране е Пирамидално сортиране (или Heapsort на английски). Той реално се възползва от свойствата на структурата данни пирамида (или heap на английски).

Идея

Погледнете статията за приоритетна опашка. Реално имплементацията, която сме описали там, е именно на пирамида.

Имплементация

Ще ползваме само части от пирамидата - по-конкретно линейното строене и изваждането на елемент. Тук ще покажем опростена имплементация, ползваща фиксиран тип int вместо темплейтен тип, но преходът до такъв е тривиален.

Отново ще ползваме масив за да пазим елементите на пирамидата, като първият елемент ще е с индекс 0, а неговите деца ще са с индекси idx * 2 + 1 и idx * 2 + 2, съответно.

Първо ни трябва функция, която по даден индекс на елемент да го "натиска" надолу в пирамидата, докато застане на такава позиция, че никое от децата му (ако има такива) да не са по-големи от него.
void
pushDown(
int
*
array
,
int
idx
,
int
len) {
while
(idx
*
2
+
1
<
len) {
int
child
=
idx
*
2
+
1
;
if
(child
+
1
<
len
&
&
array[child]
<
array[child
+
1
]) child
+
+
;
if
(array[idx]
>
=
array[child])
break
;
swap(array[child]
,
array[idx])
;
idx
=
child
;
} }

След това трябва да извършим самото сортиране по подаден масив и неговите размери. Първо го привеждаме в състояние на heap (познато като heapify), след което N на брой пъти взимаме най-големия елемент от оставащите (намиращ се на индекс 0) и го слагаме в края на масива. Забележете, че това е удобно за нас, тъй като след като го сложим в края на масива, намаляме броя елементи, които трябва да сортираме с 1 и той не ни пречи на тази позиция. Разбира се, не трябва да забравяме след като разменим най-големия елемент с най-дясното листо от последния ред на пирамидата да го "натиснем" надолу, докато застане на подходяща позиция за да се възвърне свойството на heap.
void
heapSort(
int
*
array
,
int
len) {
for
(
int
i
=
len
-
1
;
i
>
=
0
;
i
-
-
) { pushDown(array
,
i
,
len)
;
}
for
(
;
len
>
1
;
len
-
-
) { swap(array[
0
]
,
array[len
-
1
])
;
pushDown(array
,
0
,
len
-
1
)
;
} }

Най-добър и най-лош случай

!Поради това, че биват разменяни елементи на относително отдалечени места в паметта (примерно елемент с индекс 1000 в масива има деца на индекси 2001 и 2002, които са относително далеч), се оказва, че алгоритъмът почти изобщо не ползва кеша на процесора (при всяко поискване на нов елемент се прави нова заявка до истинската памет, която е относително бавна в сравнение с кеша на процесора). При Quicksort и Mergesort това не беше така - в най-дълбоките нива на рекурсията искахме да сортираме няколко последователни в паметта елемента - което е много cache friendly. По тази причина Heapsort на практика се представя няколко пъти по-бавно от Quicksort и Mergesort.
?На рандом тестове тази имплементация е около четири пъти по-бавна от вградения в STL sort().
Както и при Mergesort тук няма ясно разграничен най-добър и най-лош случай. При всяко вадене на най-голям елемент той бива заместен от (относително) малък, върху който трябва да бъде изпълнен pushDown(). Тъй като е (относително) малък, за да намери правилното си място (и така да се възстановят изискванията елементите да са в подредба на пирамида), той ще направи приблизително log(N) слизания надолу. Така алгоритъмът ще прави по (приблизително) N * log(N) операции независимо от входа.

Сортиране чрез броене (Counting Sort)

До сега говорихме само за алгоритми за сортиране, базирани на сравнения. За тях е доказано, че не могат да бъдат по-бързи от O(N∙log(N)). Не можем ли, обаче, да подобрим тази граница, като направим алгоритъм за сортиране, който не е базиран на сравнения? Оказва се, че можем, стига нещата, които сортираме, да спазват определени изисквания. Тук ще покажем най-често ползвания от тези алгоритми, наричан сортиране чрез броене, или на английски Counting Sort.

Идея

Ако искаме да сортираме N на брой числа, но знаем, че всички от тях са естествени и не по-големи от някаква относително ниска граница M, то можем да ги сортираме за O(N + M) позлвайки O(M) допълнителна памет.

Първо, заделяме масив с M клетки, инициализирани с 0. В клетка с индекс i ще броим колко пъти сме срещнали елемент със стойност i. Например, ако искаме да сортираме масива {42, 13, 2, 13, 42, 42, 17, 42}, ще заделим масив int cnt[43]. След това минаваме през входния масив и за всяко срещнато число увеличаваме съответния индекс в cnt[]. В завършването на тази процедура ще имаме cnt[2] == 1, cnt[13] == 2, cnt[17] == 1, cnt[42] == 4, а всеки друг индекс ще е останал непроменен и равен на 0.

После минаваме през целия масив cnt[] и изпечатваме всеки негов индекс по толкова пъти, колкото е числото в него. Тъй като обхождаме масива в нарастващ ред на индексите му, ще сме изпечатали 2 веднъж, после 13 два пъти, после 17 веднъж, и накрая 42 четири пъти. Което е точно което бихме направили, ако бяхме сортирали числата с някой от другите алгоритми и после ги бяхме изпечатали!

Имплементация

void
countingSort(
int
*
array
,
int
size) {
static
int
cnt[MAX_VALUE
+
1
]
;
memset(cnt
,
0
,
sizeof
(cnt))
;
for
(
int
i
=
0
;
i
<
size
;
i
+
+
) cnt[array[i]]
+
+
;
size
=
0
;
for
(
int
val
=
0
;
val
<
=
MAX_VALUE
;
val
+
+
)
while
(cnt[val]
-
-
) array[size
+
+
]
=
val
;
}

Най-добър и най-лош случай

?В зависимост от броя елементи и колко голям е най-големият от тях, този алгоритъм може да бъде многократно по-бърз от STL-ския sort().
Тъй като алгоритъмът от една страна е линеен, то това е сигурна долна граница на това колко бързо може да бъде сортирането - няма реален "най-добър" или "най-лош" случай.

От друга страна, ако имаме малко числа и искаме да ги сортираме, този алгоритъм ще направи огромен брой ненужни стъпки (тъй като инициализираме и обхождаме всички MAX_VALUE на брой клетки). В тези случаи е по-добре да ползваме някой от другите алгоритми.

Друг проблем са отрицателни числа - тях няма как да ги ползваме като индекс в масива. Можем, обаче, да намерим най-малкото от тях и да offset-нем всички така, че да станат неотрицателни. Ето и примерна имплементация, която прави това, а също така намира най-голямото число за да знае колко клетки да задели и изследва:
void
countingSortSmart(
int
*
array
,
int
size) {
if
(size
<
2
)
return
;
int
minValue
=
array[
0
]
,
maxValue
=
array[
0
]
;
for
(
int
i
=
1
;
i
<
size
;
i
+
+
) {
if
(minValue
>
array[i]) minValue
=
array[i]
;
if
(maxValue
<
array[i]) maxValue
=
array[i]
;
}
int
*
cnt
=
new
int
[maxValue
-
minValue
+
2
]
;
memset(cnt
,
0
,
sizeof
(cnt[
0
])
*
(maxValue
-
minValue
+
2
))
;
for
(
int
i
=
0
;
i
<
size
;
i
+
+
) cnt[array[i]
-
minValue]
+
+
;
size
=
0
;
for
(
int
val
=
0
;
val
<
=
maxValue
-
minValue
+
1
;
val
+
+
)
while
(cnt[val]
-
-
) array[size
+
+
]
=
val
+
minValue
;
delete
[] cnt
;
}

Задачи

Ако не сте решили Trosver в темата за сортиране, трябва да направите едно готино наблюдение =)

Друга интересна задача, която се прави с идеята на merge sort е Seating. Ако не можете да я измислите, можете да погледнете следната статия: Counting Inversions Problem.

В задачата Sorting Trimmer пък ще ви се наложи да ползвате сортиране чрез броене.

Единият начин, по който можете да направите задачата Slang, е да генерирате всички думи с липсващ подстринг, да ги запазите в един масив или вектор, да ги сортирате, и да преброите колко от тях са уникални. Тъй като потенциалният брой подстрингове е близо 100 * 50 = 5000, като при това има до 100 думи, за които трябва да го направите, бавен сортиращ алгоритъм може и да не е достатъчно бърз.

Допълнителни материали

  1. Сортиране (www.informatika.bg)
  2. Sorting Algorithm (en.wikipedia.org)
  3. Алгоритъм за сортиране (bg.wikipedia.org)
  4. Quicksort (en.wikipedia.org)
  5. Mergesort (en.wikipedia.org)
  6. Heapsort (en.wikipedia.org)
Страницата е посетена 13691 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: