Сортиране
Sorting
Различни действия при итерация.
Сортиране. Видове бавни сортирания
Сортиране. Видове бавни сортирания
В миналата тема видяхме няколко примера за задачи, в които обхождахме елементите на дадено множество (като ги сумирахме или търсихме максималния от тях). Съществуват и много други действия, които можем да прилагаме на елементите, като например да ги печатаме, да ги променяме или да ги разместваме (включително премахваме). Тук ще доразвием идеята, като ще покажем нейно приложение в един от най-често срещаните и най-основните проблеми в програмирането.
Дребни промени...
След като веднъж имаме алгоритъм за търсене, можем много лесно да променяме какво точно да правим с намерения елемент. Често, тези дребни промени водят до доста различен резултат от изпълнение на програмата ни. Примери за това са да намираме минимум вместо максимум, произведение вместо сума, и т.н.Нека например разгледаме отново последната задача от миналата тема, с дребната модификация, че не искаме да сумираме K-те най-големи елемента, ами желаем да ги изпечатаме.
Дадени са ни 1 ≤ N ≤ 1000 цели числа {A0, A1, …, AN-1}. Изпечатайте на стандартния изход K-те най-големи от тях (K ≤ N).
Можем да ползваме почти напълно идентично решение, като това на предходната задача, с тази разлика, че вместо оператора += ползваме функцията 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;
}{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) можем да изразим всички останали оператори за сравнение: <, >, <=, >=, ==, !=.- Имаме действие, с което проверяваме дали
A < B. - Ако разменим местата на A и B получаваме
B < AилиA > B(operator >). - Ако едно число не е по-малко от друго, то то е по-голямо или равно на него. Сиреч от
!(A < B)следва, чеA >= B(operator >=). - Аналогично, тъй като вече имаме >, то можем да кажем, че от
!(А > B)следваA <= B(operator <=). - Ако първото число не е по-малко от второто, и в същото време второто не е по-малко от първото, то те са равни. Това е и
if-а, който изразихме по-рано:!(A < B) && !(B < A)следваA == B(operator ==). - Ако два обекта са различни и сравними, то или първият е по-малък от втория, или вторият е по-малък от първия. Тоест от
(A < B) || (B < A)следва, чеA != B(operator !=).
| ? | Често в учебниците ще срещнете малко по-различно представяне на същото нещо: ако (A ≤ B) и (B ≤ A), следователно A == B. Това, обаче, ако се вгледате по-внимателно, е същото, което и ние изведохме, тъй като !(A < B) е еквивалентно на (B ≤ A). |
Q: Значи, ако имаме някакъв набор от обекти, между всеки два от които е дефинирана релацията "по-малко", то можем да ги сортираме, нали така?
A: Малко изненадващо, но не. Представете си, че имате
A < B, B < C, C < A. Това са всички двойки, като за всяка е дадено кой е по-малкият елемент. Ама не можете да ги сортирате.Q: Ъъъъъъ...
| ? | Ако искате сортирането да е уникално, то трябва да имате пълна (или тотална) наредба (total order). |
- Ако A ≤ B и B ≤ A, то A == B (антисиметричност).
- Ако A ≤ B и B ≤ C, то A ≤ C (транзитивност).
- Всеки елемент е по-малък или равен на себе си, тоест A ≤ A (рефлексивност).
Задача за сортиране
Така и не формулирахме строго задачата. Сега ще поправим това, като ще ползваме реалните числа като пример за обекти, които могат да бъдат сортирани.Дадени са ви N реални числа {A0, A1, …, AN-1}. Преподредете ги по такъв начин, че всяко следващо да е по-голямо или равно на предходните, след което ги изпечатайте.
Забележете, че това не е еквивалентно на задачата с изпечатването на K-те най-големи числа, при K == N. Просто нашата имплементация правеше това (добре де, в обратен ред).Алгоритми
Поради популярността си (това е една от най-често срещаните задачи в програмирането), има много, много алгоритми за сортиране. Някои от тях са бавни, други бързи; някои изискват много памет, други изискват само две допълнителни променливи; някои се пишат на три реда, други на няколко стотин. В тази тема ще разгледаме два много прости (но за съжаление - бавни) алгоритъма за сортиране, които ще ви вършат работа в почти всички задачи от реалния живот. Доста често, обаче, в състезателното програмиране те няма да са достатъчно бързи, затова малко по-късно ще научим и няколко много ефективни (оптимални) такива в темата бързи сортирания.Bubble Sort
Също така познат на български като "Метод на мехурчето". Това според мен е най-лесният и единственият, който ще ви е нужен от бавните сортиращи алгоритми. Идеята му е следната (отново обяснен използвайки числа, но работи за всякакви други множества от елементи, изпълняващи горните условия):Идея
| ? | Bubble Sort, обяснен чрез Унгарски фолклорен танц. |
Всяка двойка съседни мехурчета, за които по-голямото е "отдолу" на по-малкото разменят местата си. Това потенциално създава нови двойки мехурчета, които трябва да се разменят. Продължаваме процеса на разменяне докато съществува двойка грешно наредени такива. В момента, в който вече няма такава двойка, елементите на масива са сортирани.
Имплементация
| ? | Вместо да изпълняваме външния цикъл N пъти, можем да го правим докато на предходната итерация се е случила поне една размяна. Ако това не е така, значи всички числа са си били на мястото и можем директно да приключим изпълнението на алгоритъма. Това ни спестява известна работа, тъй като проверката дали има две грешно наредени балончета е свързана с обхождане на целия масив, докато проверката, дали сме разменили елементи на предходната итерация, е свързана само с поддържането на един булев флаг. |
| ? | В имплементацията по-долу сме пропуснали и друга възможна оптимизация, която би намалила броя операции на половина. Тъй като след първата итерация знаем, че най-големият елемент е изплувал най-отгоре, то няма кой повече да го премести оттам. Аналогично, след K-тата итерация, най-големите K са най-отгоре и те повече няма да бъдат местени. Затова можем да не ги разглеждаме, въртейки вътрешният цикъл до arrayLength - 1 - i. |
Така имаме два (вложени) цикъла. Единият (външният) пуска под-алгоритъма за изплуване отново и отново, докато това теоретично би довело до размяна на мехурчета (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 е нещо различно. |
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 заедно с библиотеките в началото на сорса си, независимо, че по-нататък може да не го ползват.Задачи
Три задачи, които можете да решите ползвайки тези алгоритми, са:- Seating - Easy - Bubble Sort
- Medians - Easy - Insertion Sort
- Substring Sorter - което и да е сортиране
- Max Number - трябва да измислите специфична функция за сравнение и да сортирате числата ползвайки нея
- Trosver - трябва да направите едно интересно наблюдение =)
Допълнителни материали
- Бързи сортиращи алгоритми (www.informatika.bg)
- Sorting Algorithm (en.wikipedia.org)
- Алгоритъм за сортиране (bg.wikipedia.org)
- Bubble Sort (en.wikipedia.org)
- Selection Sort (en.wikipedia.org)
- Insertion Sort (en.wikipedia.org)
- Bubble Sort with Hungarian folk dancing (youtube.com)
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 17473 пъти.