Сортиране

Sorting

Различни действия при итерация.
Сортиране. Видове бавни сортирания
Автор: Александър Георгиев

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

Дребни промени...

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

Нека например разгледаме отново последната задача от миналата тема, с дребната модификация, че не искаме да сумираме K-те най-големи елемента, ами желаем да ги изпечатаме.
Дадени са ни 1 ≤ N ≤ 1000 цели числа {A0, A1, …, AN-1}. Изпечатайте на стандартния изход K-те най-големи от тях (KN).
Можем да ползваме почти напълно идентично решение, като това на предходната задача, с тази разлика, че вместо оператора += ползваме функцията fprintf().
int
printKLargest(
int
N
,
int
A[
1024
]
,
int
K) {
static
bool
vis[
1024
]
;
for
(
int
i
=
0
;
i
<
N
;
i
+
+
) vis[i]
=
false
;
int
ans
=
0
;
for
(
int
i
=
0
;
i
<
K
;
i
+
+
) {
int
idx
=
-
1
;
for
(
int
c
=
0
;
c
<
N
;
c
+
+
) {
if
(
!
vis[c]
&
&
(idx
=
=
-
1
|
|
A[idx]
<
A[c])) idx
=
c
;
} fprintf(
stdout
,
"%d\n"
,
A[idx])
;
vis[idx]
=
true
;
}
return
ans
;
}
Какво би изпечатала програмата, ако при викането ѝ K е равно на N? С известно гледане на кода и малко мислене можем да видим, че това ще са всички входни числа, но евентуално не в реда, в който са ни дадени. Тъй като във всяка вътрешна итерация намираме най-голямото неизползвано число, то логично е да очакваме резултатът от викането на функцията да са входните числа, изпечатани в намаляващ ред. Например за {42, 1, 13, 17, 666, 10, 10, 1337} резултатният ред би бил {1337, 666, 42, 17, 13, 10, 10, 1}.

...водят до Сортиране!

Добре де, не винаги до сортиране. Но в случая доведоха до това. Редица от числа, в която всяко е по-голямо или равно на тези след него, се нарича редица, сортирана в низходящ ред. Ако пък беше наобратно - най-малките числа бяха първи (и растяха нататък в редицата), то тя би била сортирана във възходящ ред. Всъщност по-често ще сортираме числа (и като цяло обекти) във възходящ ред, тъй като той е по-стандартен и интуитивен за нас. Например книгите в една библиотека са сортирани по азбучен (или лексикографски) ред.

Q: Wait, wait... Как така сортирани? Нали имената на книгите не са числа?

A: Ами да. Но някой да е казал, че можем да сравняваме единствено числа? Със същия успех можем да сравняваме и стрингове - например как са номерирани учениците в класа ви? Отново по азбучен ред на имената им. Но това изобщо не ни ограничава - освен числа и стрингове, можем да сортираме всякакви обекти, които имат дефинирана релация "по-малко" (също позната като operator <) и между тях има (поне) частична наредба спрямо тази релация. Понякога може да има и по-сложна релация за сравнение. Например, в моето училище до 7-ми клас, първо бяха момичетата, а после момчетата, като хората с еднакъв пол бяха сортирани лексикографски. Така, макар и името ми да започва с 'А', бях номер 11 в класа.

Q: Хм, ами тогава какво правим с обекти с еднаква стойност? Примерно равни числа, или книги с еднакво име?

A: В общия случай ако два обекта са с еднаква стойност, то няма да ни интересува как точно са наредени помежду си те. Например нека имаме {1, 3, 3, 7} и {1, 3, 3, 7}. Във втората наредба двете тройки са разменени (facepalm). Ама не виждате разлика, нали? Почти винаги няма да има значение как са наредени помежду си еднаквите предмети, с изключение на редки случаи. В тях просто ще трябва да дефинирате по-конкретен operator <, който да ви върши работа.

Q: Добре, хубаво, ама ако дефинираме само знака по-малко, то как ще знаем, че две числа са еднакви?

A: Конкретно за сортирането не ни трябва да правим никъде проверка за равно. Но в много други места ще ни е нужна (например ако търсим дали даден елемент се съдържа в множество). Все пак, оператор < ни е достатъчен. Питате се защо? Вижте магия:

if (!(A < B) && !(B < A)) fprintf(stdout, “A == B\n”);
Q: Ъъъъъъ... този иф изглежда като да е еквивалентен на if (A == B). Как точно се получи това?

A: Оператор < е по-мощен, отколкото изглежда на пръв поглед. С него (и логическите оператори NOT, AND и OR) можем да изразим всички останали оператори за сравнение: <, >, <=, >=, ==, !=.
  1. Имаме действие, с което проверяваме дали A < B.
  2. Ако разменим местата на A и B получаваме B < A или A > B (operator >).
  3. Ако едно число не е по-малко от друго, то то е по-голямо или равно на него. Сиреч от !(A < B) следва, че A >= B (operator >=).
  4. Аналогично, тъй като вече имаме >, то можем да кажем, че от !(А > B) следва A <= B (operator <=).
  5. ?Често в учебниците ще срещнете малко по-различно представяне на същото нещо: ако (A ≤ B) и (B ≤ A), следователно A == B. Това, обаче, ако се вгледате по-внимателно, е същото, което и ние изведохме, тъй като !(A < B) е еквивалентно на (B ≤ A).
  6. Ако първото число не е по-малко от второто, и в същото време второто не е по-малко от първото, то те са равни. Това е и if-а, който изразихме по-рано: !(A < B) && !(B < A) следва A == B (operator ==).
  7. Ако два обекта са различни и сравними, то или първият е по-малък от втория, или вторият е по-малък от първия. Тоест от (A < B) || (B < A) следва, че A != B (operator !=).

Найс, а?

Q: Значи, ако имаме някакъв набор от обекти, между всеки два от които е дефинирана релацията "по-малко", то можем да ги сортираме, нали така?

A: Малко изненадващо, но не. Представете си, че имате A < B, B < C, C < A. Това са всички двойки, като за всяка е дадено кой е по-малкият елемент. Ама не можете да ги сортирате.

Q: Ъъъъъъ...

?Ако искате сортирането да е уникално, то трябва да имате пълна (или тотална) наредба (total order).
A: Това, което пропуснахме, е така наречената "частична наредба". Тук няма да се впускаме надълго и нашироко какво е това (ще имате това невероятно удоволствие в университета), като единственото, което трябва да знаете, е, че за да можете да сортирате (безпроблемно) някакво множество от обекти, то трябва да са изпълнени следните три неща:
  1. Ако A ≤ B и B ≤ A, то A == B (антисиметричност).
  2. Ако A ≤ B и B ≤ C, то A ≤ C (транзитивност).
  3. Всеки елемент е по-малък или равен на себе си, тоест A ≤ A (рефлексивност).

Задача за сортиране

Така и не формулирахме строго задачата. Сега ще поправим това, като ще ползваме реалните числа като пример за обекти, които могат да бъдат сортирани.
Дадени са ви N реални числа {A0, A1, …, AN-1}. Преподредете ги по такъв начин, че всяко следващо да е по-голямо или равно на предходните, след което ги изпечатайте.
Забележете, че това не е еквивалентно на задачата с изпечатването на K-те най-големи числа, при K == N. Просто нашата имплементация правеше това (добре де, в обратен ред).

Алгоритми

Поради популярността си (това е една от най-често срещаните задачи в програмирането), има много, много алгоритми за сортиране. Някои от тях са бавни, други бързи; някои изискват много памет, други изискват само две допълнителни променливи; някои се пишат на три реда, други на няколко стотин. В тази тема ще разгледаме два много прости (но за съжаление - бавни) алгоритъма за сортиране, които ще ви вършат работа в почти всички задачи от реалния живот. Доста често, обаче, в състезателното програмиране те няма да са достатъчно бързи, затова малко по-късно ще научим и няколко много ефективни (оптимални) такива в темата бързи сортирания.

Bubble Sort

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

Идея

?Bubble Sort, обяснен чрез Унгарски фолклорен танц.
Представете си масива от числа наредени не хоризонтално, ами вертикално (като първата позиция е най-отдолу, последната - най-отгоре). Сега си представете, че това се случва под вода, а елементите на масива са мехурчета, всяко съдържащо толкова грама въздух, колкото е числото в него. По-големите мехурчета ще изплуват по-нагоре, тъй като повечето въздух ги дърпа по-силно натам (в това обяснение не се стремим към физична акуратност).

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

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

?Вместо да изпълняваме външния цикъл N пъти, можем да го правим докато на предходната итерация се е случила поне една размяна. Ако това не е така, значи всички числа са си били на мястото и можем директно да приключим изпълнението на алгоритъма. Това ни спестява известна работа, тъй като проверката дали има две грешно наредени балончета е свързана с обхождане на целия масив, докато проверката, дали сме разменили елементи на предходната итерация, е свързана само с поддържането на един булев флаг.
?В имплементацията по-долу сме пропуснали и друга възможна оптимизация, която би намалила броя операции на половина. Тъй като след първата итерация знаем, че най-големият елемент е изплувал най-отгоре, то няма кой повече да го премести оттам. Аналогично, след K-тата итерация, най-големите K са най-отгоре и те повече няма да бъдат местени. Затова можем да не ги разглеждаме, въртейки вътрешният цикъл до arrayLength - 1 - i.
Как имплементираме това като код? Започвайки с най-лявото число (мехурче), почваме да го движим надясно ("изплуваме"), докато стигнем до друго, по-голямо (лесно-изплуващо) такова. В този случай не трябва да ги разменяме, а вместо това грабваме по-голямото и почваме да движим него надясно (нагоре). По някое време ще сме стигнали до най-голямото и то ще изплува до последната позиция (където и трябва да се намира). След това отново хващаме текущото най-ляво (долно) балонче и прилагаме тази процедура и с него. Тъй като на всяка итерация едно от балончетата "изплува" до крайната си позиция, ще са ни нужни най-много N итерации.

Така имаме два (вложени) цикъла. Единият (външният) пуска под-алгоритъма за изплуване отново и отново, докато това теоретично би довело до размяна на мехурчета (N пъти). Другият (вътрешен) цикъл имплементира самото изплуване.

Следва примерна имплементация:
void
bubbleSort(
int
*
array
,
int
arrayLength) {
for
(
int
i
=
0
;
i
<
arrayLength
;
i
+
+
) {
for
(
int
c
=
0
;
c
<
arrayLength
-
1
;
c
+
+
) {
if
(array[c]
>
array[c
+
1
]) { swap(array[c]
,
array[c
+
1
])
;
} } } }

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

?Макар и да е логично сортиращ алгоритъм да се справя бързо, когато входът е почти (или изцяло) сортиран, както е при Bubble Sort, това не винаги е така. Както ще видим по-късно, при една от по-простите имплементации на Quick Sort точно сортиран (правилно) вход е най-тежкият случай, който може да се падне.
Не изглежда много сложно, нали? Като цяло алгоритъмът приключва бързо, ако входният масив е "почти сортиран" и много бавно, ако е много-разбъркан.

Очевидно, най-добрият случай е ако масивът вече е сортиран - тогава ще направим една единствена итерация, в която няма да разменим нито една двойка балончета, и ще приключим. Можете ли да се досетите кой е най-лошият възможен случай?

Отговорът е, че алгоритъмът се представя най-зле, когато числата са сортирани точно наобратно. Тогава на първата итерация ще разменим N-1 двойки числа, на втората - N-2, на третата - N-3 и т.н. На последната итерация ще разменим само една двойка. Можете ли да сметнете колко размени правим общо? Отговорът е (N-1) + (N-2) + … + 2 + 1, което е N * (N-1) / 2. Сами можете да сметнете, че това е сравнително неприемливо за голям брой числа. За да сортирате ЕГН-тата на всички хора в България, ще ви трябват около 27 трилиона размени, което ще ви отнеме около седем часа. По-късно, обаче, ще разгледаме алгоритми, които ще се справят с това за под секунда.

Selection Sort

На български се нарича "метод на пряката селекция", тъй като основната му идея е на всяка стъпка да селектираме елемента, който е наред да сложим в изходния масив. Единственият случай, в който бихме желали да го ползваме вместо Bubble Sort, е ако елементите са големи (примерно структури с много данни в тях) и не искаме да ги размотаваме насам-натам ненужно, тъй като той прави много по-малко размени (но същия брой сравнения) на елементи.

Идея

Правим N стъпки, като в i-тата стъпка намираме i-тия по големина елемент от входния масив и го слагаме на i-та позиция. Тъй като на i-та позиция ще има друг елемент, който трябва да преместим някъде, можем просто да го сложим на позицията, където до сега се е намирал i-тия по големина (просто да ги разменим).

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

Просто имплементираме горната идея, нищо специално.
void
selectionSort(
int
*
array
,
int
arrayLength) {
for
(
int
i
=
0
;
i
<
arrayLength
;
i
+
+
) {
int
idx
=
i
;
for
(
int
c
=
i
+
1
;
c
<
arrayLength
;
c
+
+
) {
if
(array[c]
<
array[idx]) idx
=
c
;
} swap(array[i]
,
array[idx])
;
} }

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

Този алгоритъм няма най-добър и най-лош случай - при него всички случаи са еднакво добри/лоши (в зависимост дали сте оптимисти или песимисти), тъй като при всяка външна итерация (селекция) обхождаме всички елементи за да намерим този, който трябва да отиде на позиция i. Това си има както предимства, така и недостатъци. Главното предимство е, че много лесно можем да тестваме как се държи алгоритъма ни (като скорост) и не се страхуваме от гадни тестове. Недостатъкът е, че липсват подобренията в бързодействието при почти-сортиран вход или при рандом вход (където Bubble Sort се държи около два пъти по-бързо, отколкото в най-лошия си случай).

Ако имаме масив с N елемента, то ние правим N селекции, във всяка от които обхождаме всички елементи надясно от текущата позиция, което прави N * (N + 1) / 2 операции. Забележете, че това е точно колкото при Bubble Sort, само че тук операциите са само сравнения, а не размени (имаме само N на брой размени).

Insertion Sort

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

Идея

Правим N стъпки, като след i-тата стъпка сме сортирали първите i елемента. Първата стъпка можем да пропуснем, тъй като един елемент сам по себе си е сортиран. На втората стъпка ще сме сортирали първите два елемента. След третата стъпка ще сме сортирали първите три, и така нататък, докато на последната ще сме сортирали всички елементи.

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

На i-тата стъпка трябва да "вмъкнем" i-тия елемент във вече сортираните i-1. Това става лесно, именно защото те вече са сортирани - можем да тръгнем от дясната страна на вече сортирания префикс на масива и да разменяме i-тия елемент с левите му, докато отиде на мястото си. Това е подобно на bubble sort "изплуването", с тази разлика, че когато елементът стигне до мястото си (не е по-малък от левия си) спираме веднага, тъй като знаем, че останалите са вече сортирани.
void
insertionSort(
int
*
array
,
int
arrayLength) {
for
(
int
i
=
1
;
i
<
arrayLength
;
i
+
+
) {
for
(
int
idx
=
i
;
idx
>
0
&
&
array[idx]
<
array[idx
-
1
]
;
idx
-
-
) { swap(array[idx]
,
array[idx
-
1
])
;
} } }

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

Този алгоритъм реално мести всеки елемент толкова позиции, колкото е разстоянието му от позицията, която ще заема в сортирания масив. Реално, ако масивът е почти сортиран той се представя много добре. Да кажем, че елементът, който е най-далеч от крайната си позиция е на разстояние D. Алгоритъмът ще направи N * D операции. Най-добрият случай е при почти сортиран масив, в който случай алгоритъмът ще направи около N операции.

Обратно, най-лошият случай е очевидно когато елементите са най-далеч от крайната им позиция - примерно сортиран наобратно масив, в който този алгоритъм би направил около N * N / 2 операции.

Gnome Sort

Не много известен, но все пак интересен алгоритъм е Gnome Sort. Името му идва от неговия малък (гномски) код.

Идея

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

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

Всъщност имплементацията е почти същата като на Insertion Sort, само че се имплементира с един единствен цикъл.
void
gnomeSort(
int
*
array
,
int
arrayLength) {
for
(
int
idx
=
1
;
idx
<
arrayLength
;
idx
+
+
) {
if
(idx
>
0
&
&
array[idx]
<
array[idx
-
1
]) { swap(array[idx]
,
array[idx
-
1
])
;
idx
-
=
2
;
} } }

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

Почти сходен с Insertion Sort (реално е просто друга имплементация), най-добрият и най-лошият случай са същите. Gnome Sort прави около два пъти повече операции.

In-place vs. out-of-place

Забелязахте ли, че при метода на мехурчето не използвахме почти никакви допълнителни променливи? Е, ползвахме променливи за циклите, а също така има и една скрита
?Както ще видим в темата за сложност на алгоритми, много често константната допълнителна памет се изключва от сметките, тъй като е пренебрежимо малко в сравнение с размера на самите данни. На кого му пука за няколко байта повече или по-малко?
променлива, която ни е нужна за да разменяме елементите във функцията swap(), но това беше всичко - три допълнителни променливи, независимо колко елемента има в масива, който сортираме. Това се нарича константна допълнителна памет и в общия случай се счита за хубаво нещо, тъй като не зависи от обема данни, които алгоритъмът обработва.

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

От друга страна, имплементацията на printKLargest(), която показахме съвсем в началото на темата, ползваше нов (допълнителен) масив, в който пазихме кои елементи вече сме "използвали". Тъй като размерът на този масив трябва да е колкото е и големината на входния такъв, то казваме, че заема линейна допълнителна памет. Ако входният масив има N елемнта, то толкова ще трябва да има и допълнителният. Ако входният масив има 2N елемента, то и допълнителният ще има 2N елемента. Ако има 100N елемента, допълнителният също ще има 100N елемента. Тоест размерът на новия масив расте линейно с размера на входния такъв.

Този тип алгоритми пък се нарича out-of-place, тъй като ползваме памет, която сме поискали допълнително. Някои сортиращи алгоритми (като например Merge Sort, който ще разгледаме в темата за бързи сортирания) не могат да бъдат имплементирани по друг начин.

STL Sort

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

?"std" идва като съкращение от "standard". И се пише с малки букви. STD е нещо различно.
Популярността на сортирането е довела до нуждата да бъде включено в стандартната библиотека на почти всички модерни програмни езици. C++ не е изключение, като разполагате с много добра (бърза) имплементация. За да я ползвате, трябва да включите (include-нете) в програмата си библиотеката <algorithm>, след което да извикате функцията sort(array, array + arrayLength). array е името на масива, който искате да сортирате, докато arrayLength е неговата дължина (брой елементи). Функцията sort() приема два итератора, като за момента можете да считате, че това са начало и край на паметта, в която се намират елементите. Всъщност даже забравете това, просто запомнете как се ползва (с масиви) :) По-късно в темата за стандартната библиотека на C++ ще разгледаме какво е итератор и как се ползва сортиране с него.

!Забележете, че масивът array има 10 елемента, но само 8 от тях са инициализирани и в последствие сортирани. Това не бърка функцията sort(), тъй като тя обработва само паметта от първия итератор (array) до втория такъв (array + 8).
Поради причини, които за момента изобщо не ви касаят, трябва или пред името на функцията да имате std:: (тоест така я викате със std::sort(array, arrayLength), или след включването на библиотеките да имате using namespace std;. Тъй като и двете са донякъде объркващи, ето два кратки примера, които илюстрират начина на ползване на функцията.

Използвайки std::
#include <cstdio>
#include <algorithm>
int
main(
void
) {
int
array[
10
]
=
{
42
,
1
,
13
,
17
,
666
,
10
,
10
,
1337
}
;
std
:
:
sort(array
,
array
+
8
)
;
for
(
int
i
=
0
;
i
<
8
;
i
+
+
) fprintf(
stdout
,
"%d%c"
,
array[i]
,
i
=
=
7
?
'\n'
:
' '
)
;
return
0
;
}

Използвайки using namespace std;
#include <cstdio>
#include <algorithm>
using
namespace
std
;
int
main(
void
) {
int
array[
10
]
=
{
42
,
1
,
13
,
17
,
666
,
10
,
10
,
1337
}
;
sort(array
,
array
+
8
)
;
for
(
int
i
=
0
;
i
<
8
;
i
+
+
) fprintf(
stdout
,
"%d%c"
,
array[i]
,
i
=
=
7
?
'\n'
:
' '
)
;
return
0
;
}

В професионален код почти винаги се предпочита да се ползва std:: пред using namespace std. За състезания, обаче, това е по-скоро наобратно. Тъй като STL се ползва много (особено при по-сложни задачи), често състезателите пишат и using namespace std заедно с библиотеките в началото на сорса си, независимо, че по-нататък може да не го ползват.

Задачи

Три задачи, които можете да решите ползвайки тези алгоритми, са:
  1. Seating - Easy - Bubble Sort
  2. Medians - Easy - Insertion Sort
  3. Substring Sorter - което и да е сортиране
  4. Max Number - трябва да измислите специфична функция за сравнение и да сортирате числата ползвайки нея
  5. Trosver - трябва да направите едно интересно наблюдение =)

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

  1. Бързи сортиращи алгоритми (www.informatika.bg)
  2. Sorting Algorithm (en.wikipedia.org)
  3. Алгоритъм за сортиране (bg.wikipedia.org)
  4. Bubble Sort (en.wikipedia.org)
  5. Selection Sort (en.wikipedia.org)
  6. Insertion Sort (en.wikipedia.org)
  7. Bubble Sort with Hungarian folk dancing (youtube.com)


За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 5696 пъти.

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

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

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