Сортиране

В никакъв случай не забравяй да сложиш заглавие тук!

Здрасти, днес ще си подреждаме пластмасовите войници по височина.

Как се сортират данни?

Няма един-най-добър-начин. Сори.
В повечето случаи има един-достатъчно-добър-начин.

Quicksort стига за почти всичко.
За останалото стига Heapsort.

Mergesort също е много добро и има случаи, в които е по-хубаво от другите!

Има, разбира се, и много по-сложни алгоритми отнасящи се до темата(MapReduce, Hadoop). Няма да ги учим сега, но са интересни и нужни за най-големите проекти.

Изисквания

Един хубав алгоритъм работещ на домашен компютър трябва да може да сортира 1 000 000 числа за една секунда без дори да се задъха.
10 000 000 числа на секунда също не е изключено.

На практика, добре би било и да може да му се поставят някакви ограничения:
Да сортира нещата използвайки не много RAM(дори и това да го забави малко).
Да намери бързо няколко от най-малките/големите елементи в масив(за да може веднага да продължим работа), а другите - когато успее.
Да няма нужда от всички данни предварително, а да ги сортира "докато пристигат". Това преди е било полезно за данни записани на лента, а в днешно време - за данни идващи от Интернет.

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

Защо ми е да го знам това?

Защото сортирането е най-често извършваната от компютри операция.
Според някои изследвания 25-40% от цялото време, през което компютри са работили, е използвано за сортиране.
Почти всяка операция, която се извършва върху сортирани данни е многократно по-бърза(така де, ако речникът не беше подреден по азбучен ред, щеше да има да търсиш какво означава "Асимптотично").

Сайт с информация:

Ето един сайт, който ми се искаше да бях написал аз:
http://www.sorting-algorithms.com/
Тук има повечето важни неща за алгоритмите, както и много много готини анимацийки.

Кои неща са важни?

Скорост

Най-най значимото нещо за едно сортиране е колко е бързо.
Това на теория се изразява с асимптотична нотация, но всъщност всички значими алгоритми са O(NlogN).
Доказано е, че по-бързи няма как да станат, затова се гледат и константите. NlogN > 0.8NlogN.

Памет (In-place)

Ако е казано, че един алгоритъм сортира In-place, това означава, че не му трябва допълнителна памет(или, по-точно, трябва му само някакво минимално O(1) количество памет за временни променливи и подобни неща).
Ако за сортирането е нужно да копира целия масив някъде, това не е in-place сортиране.

Паралелизируемост

Това напоследък става все по-важна тема.
Както е добре известно, процесорите няма да стават много по-бързи, отколкото са в момента. Но ще стават повече на брой в един компютър.
Ако един алгоритъм работи 2 пъти по-бързо когато се пусне на 2 процесора, това е хубаво. На практика 1.5 пъти по-бързо също е хубаво.
Ако може да се пусне на N процесора и да работи N/2 пъти по-бързо - това е много хубаво. Мацките си падат по паралелизируеми алгоритми.

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

Стабилност

Имаме масив от обекти, които имат две променливи A и B(примерно, име и възраст).
Стабилно е такова сортиране, при което ако сортираме масив по A, а след това го сортираме и по B, той остава сортиран и по A.

Име Възраст
Alexander Anderson 65
Alucard 400
Seras Victorial 19
Integra Hellsing 22
Walter C. Dornes 77

В някои случаи е полезно, в някои случаи няма значение.
Аз, например, наистина искам героите в Hellsing сортирани по име, както и по възраст.
Което, реалистично погледнато, е малко глупаво, защото никои двама не се казват еднакво. Така де, "в някои случаи няма значение".

Други

Понякога има и други критерии. Например, ако сортираме много малко числа(n <= 20, да кажем), то най-"глупавите" стратегии всъщност работят най-добре.
Ако 10 000 пъти сортираме по 10 числа, пряка селекция ще работи по-добре от mergesort.

Сравнение на сортиранията

QuickSort

Алгоритъм:
Вземаме произволен елемент от масива. Кръщаваме го X.
Пренареждаме масива по следния начин:

  1. Елементи по-малки от X.
  2. X.
  3. Елементи по-големи от X.

Прилагаме алгоритъма рекурсивно на части 1) и 3).

Това какво ни дава?

  • X е на правилното си място в масива.
  • Масиви от по 1 елемент са си сортирани винаги(т.е. тогава рекурсията свършва).
  • Ако приемем, че 1) и 3) биват сортирани успешно, то следва че и целият масив бива сортиран успешно.

Самото пренареждане на масива не е напълно тривиално, но има как да се направи.

Скорост:
$\mathbf{O}(N^2)$ в най-лошия случай. Известни модификации на алгоритъма гарантират, че този сценарий кажи-речи никога няма да се достигне.
Средно времетраенето му е O(NlogN). Това е бърз алгоритъм.

Памет:
In-place.

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

Стабилност:
Не е стабилно.

HeapSort

Използва стуктурата от данни Пирамида.
Тя поддържа добавяне на елемент за O(logN) време, както и изваждане на максималния елемент за O(logN) време.

Алгоритъм:
Просто пъхаме всички N елементи в пирамидата, после ако N пъти извадим максимума, ще имаме елементите в сортиран ред.

Скорост:
O(NlogN)
Памет:
In-place.
Паралелизируемост:
Не особено.
Стабилност:
Не е стабилно.

MergeSort

Алгоритъм:
Разделяме масива на две (почти) равни части.
Сортираме всяка от тези части - рекурсивно с MergeSort или с нещо друго.
Merge-ваме двете сортирани части в нов, сортиран масив.
Връщаме този нов масив.

Операцията Merge е специална, но все пак лесна:
Имаме 2 сортирани масива, А и B. Трябва да получим трети, C, сортиран, съдържащ всички елементи на първите два.
Гледаме на кой от A и B най-големият елемент е по-голям(той винаги е на първо място в тях). Нека този елемент е X.
Махаме X откъдето сме го взели, слагаме го в C.
Повтаряме докато не се изпразнят и двата масива.

Пример:
A = 6 5 3 2 2 1
B = 5 4 3 1 1

Step C A B
1 [] [6 5 3 2 2 1] [5 4 3 1 1]
2 [6] [5 3 2 2 1] [5 4 3 1 1]
3 [6 5] [3 2 2 1] [5 4 3 1 1]
4 [6 5 5] [3 2 2 1] [4 3 1 1]
5 [6 5 5 4] [3 2 2 1] [3 1 1]
6 [6 5 5 4 3] [2 2 1] [3 1 1]
7 [6 5 5 4 3 3] [2 2 1] [1 1]
8 [6 5 5 4 3 3 2] [2 1] [1 1]
9 [6 5 5 4 3 3 2 2] [1] [1 1]
10 [6 5 5 4 3 3 2 2 1] [] [1 1]
11 [6 5 5 4 3 3 2 2 1 1] [] [1]
12 [6 5 5 4 3 3 2 2 1 1 1] [] []

Скорост:
О(NlogN)
Ако се паралелизира, това е МНОГО МНОГО по-бързо от останалите. Най-модерните сортиращи алгоритми успяват да обработят терабайт данни за няколко минути.
Не ползват точно MergeSort, но от него са тръгнали и с определени модификации постигат завидни резултати.

Не изисква всички данни да са налице когато започне работа - просто сортира каквото има, а каквото дойде по-късно си го Merge-ва в някой бъдещ момент.

Памет:
Масивът трябва да се копира насам-натам.

Паралелизируемост:
Този алгоритъм буквално е Примерът за многопроцесорни алгоритми.
Двата подмасива могат да се сортират независимо на 2 процесора.
Ако те се разбият всеки на по още два, това става на 4 процесора.
Или пък, може един масив да се разбие на 100 части - за 100 процесора. Небето е границата.

Стабилност:
Стабилен е.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License