2. Сортиране

2.1. Сортиране на вмъкване

Един от най-простите начини за сортиране на масив е сортирането чрез вмъкване. В обикновения живот се сблъскваме с този метод, когато играем карти. За да сортирате картите, които имате, изваждате карта, плъзгате останалите карти и след това поставяте картата на място. Процесът се повтаря, докато поне една карта не е на мястото си. И средното, и най-лошото време за този алгоритъм е O(n 2). Допълнителна информация може да бъде намерена в книгата на Кнут [1].

На фиг. 2.2(a) изваждаме елемент 3. След това преместваме елементите, разположени по-горе, докато намерим мястото, където трябва да вмъкнем 3. Този процес продължава на фиг. Фигура 2.1(b) за числото 1. Накрая, във Фигура 2.1(c) завършваме сортирането, като поставяме 2 на правилното място.

Ако масивът ни е дълъг n, трябва да итерираме n - 1 елемента. Всеки път може да се наложи да изместим n - 1 други елемента. Ето защо този метод е доста трудоемък.

Сортирането чрез вмъкване е един от методите за сортиране на място. С други думи, не изисква допълнителна памет, ние сортираме елементите на масива, използвайки само паметта, заета от самия масив. Освен това е стабилен - ако сред сортираните ключове има еднакви ключове, след сортирането те остават в първоначалния си ред.

Внедряване

Реализация на сортиране чрез вмъкване в C може да бъде намерена в раздел 4.1. Операторътtypedef Tи операторът за сравнениеcompGTтрябва да бъдат променени, за да съответстват на данните, съхранени в таблицата.

2.2. Сортиране на черупки

Методът, предложен от Donald L. Schell, е нестабилен сорт на място. Ефективността на метода Shell се обяснява с факта, че изместените елементи бързо падатправилните места. Средното време за сортиране на Shell е O(n 1.25), оценката за най-лошия случай е O(n 1.5). За допълнителни препратки вижте книгата на Кнут [1].

На фиг. 2.2(a) беше пример за сортиране чрез вмъкване. Първо извадихме 1, след това изместихме 3 и 5 с една позиция надолу, след което вкарахме 1. Така ни трябваха две смени. Следващия път ни трябваха две смени, за да вмъкнем на правилното място 2. За целия процес ни трябваха 2 + 2 + 1 = 5 смени.

На фиг. 2.2(b) илюстрира Shellort. Започваме, като правим сортиране чрез вмъкване на стъпки от 2. Първо разглеждаме числата 3 и 1: извличаме 2, преместваме 3 по 1 на стъпки от 2, вмъкваме 2. След това повтаряме същото за числата 5 и 2: извличаме 2, преместваме надолу 5, вмъкваме 2. И така нататък. След като завършим сортирането със стъпка 2, го изпълняваме със стъпка 1, т.е. извършете нормално сортиране на вмъкване. Общо имаме нужда от 1 + 1 + 1 = 3 смени. Така, използвайки стъпка по-голяма от 1 в началото, постигнахме по-малък брой смени.

Можете да използвате различни схеми за избор на стъпки. Като правило, първо сортираме масива с голяма стъпка, след това намаляваме стъпката и повтаряме сортирането. В самия край сортираме със стъпка 1. Въпреки че този метод е лесен за обяснение, неговият формален анализ е доста труден. По-специално, теоретиците не успяха да намерят оптимална схема за избор на стъпки. Knuth [1] направи много експерименти и следната формула за избор на стъпки (h) за масив с дължина N:

в последователността h1 = 1, hs + 1 = 3hs + 1. вземете ht, ако ht + 2 і N.

Ето първите няколко стойности на h:h1= 1h2= (3 x 1) + 1 = 4h3= (3 x 4) + 1 = 13h4= (3 x 13) + 1 = 40h5= (3 x 40) + 1 = 121

Да сортираммасив с дължина 100, първо намираме числото s, за което hs і 100. Според дадените цифри s = 5. Стойността, от която се нуждаем, е два реда по-горе. Така последователността от стъпки за сортиране ще бъде: 13-4-1. Е, разбира се, не е необходимо да съхраняваме тази последователност: следващата стойност на h се намира от предишната с помощта на формулатаhs - 1 = hs / 3

Внедряване

За изпълнение на Shellsort в C, вижте раздел 4.2. Операторътtypedef Tи операторът за сравнениеcompGTтрябва да бъдат променени, за да съответстват на данните, съхранени в масива. Основната част от алгоритъма е сортиране чрез вмъкване със стъпка h.

2.3. Бързо сортиране

Въпреки че идеята на Shell значително подобрява сортирането при вмъкване, все още има място за подобрение. Един от най-известните алгоритми за сортиране е бързото сортиране, предложен от C. Hoor. Методът наистина е много бърз, неслучайно на английски се нарича QuickSort за недоволство на всички проверяващи правописа („Извинете Шишков: не знам как да превеждам“).

Този метод изисква O(n lg n) средно и O(n 2 ) в най-лошия случай. За щастие, ако се вземат адекватни предпазни мерки, най-лошият случай е изключително малко вероятен. Бързото търсене не е устойчиво. Освен това се нуждае от стек, т.е. това също не е метод за сортиране на място. Допълнителна информация може да бъде намерена в статията на Kormen [2].

Алгоритъмът разделя сортируемия масив на секции, след което рекурсивно сортира всяка секция. Във функциятаДял(фиг. 2.3) един от елементите на масива се избира като централен. Ключовете, по-малки отцентралния, трябва да бъдат поставени вляво от него, тези, които са по-големи - вдясно.

На фиг. 2.4(a) За централен елемент е избран елемент 3. Индексите започват да се променят от краищата на масива.Индекс i започва отляво и се използва за избиране на елементи, които са по-големи от центъра, индекс j започва отдясно и се използва за избиране на елементи, които са по-малки от центъра. Тези елементи са разменени - виж фиг. 2.4(b). Процедурата QuickSort рекурсивно сортира два подмасива, което води до масива, показан на фигура 2. 2.4(c).

ФункциятаPartitionможе просто да вземе първия елемент (A[Lb]) като централна функция. Сравняваме всички останали елементи от масива с централния и го преместваме наляво или надясно. Има обаче един случай, който безмилостно унищожава тази красива простота. Да приемем, че нашият масив е сортиран от самото начало. ФункциятаPartitionвинаги ще получава минималния елемент като централен и следователно ще разделя масива по най-лошия начин: съответно ще има един елемент в левия дял, Ub - Lb елементи ще останат в десния дял. По този начин всяко рекурсивно извикване на процедурата за бързо сортиране само ще намали дължината на сортирания масив с 1. В резултат на това ще са необходими n рекурсивни извиквания за завършване на сортирането, което води до време за изпълнение на алгоритъма от порядъка на O(n 2 ). Един от начините за преодоляване на този проблем е да изберете произволно централния елемент. Това ще направи най-лошия случайизключителномалко вероятен.

Внедряване

Реализацията на алгоритъма в C е в раздел 4.3. Изявлениятаtypedef TиcompGTтрябва да бъдат променени, за да съответстват на данните, съхранени в масива. В сравнение с основния алгоритъм има някои подобрения:

Елементът, разположен в средата, е избран като централен елемент във функциятаpartition. Този избор подобрява оценката на средното време за работа, ако масивът е само частично подреден. Най-лошотоза тази реализация ситуацията възниква, когато всеки пътдялът. Максималният или минималният елемент се избира като централен.
За кратки масиви се извикваinsertSort. Поради рекурсия и други "режийни разходи", бързото търсене не е толкова бързо за кратки масиви. Следователно, ако масивът има по-малко от 12 елемента, се извиква сортиране чрез вмъкване. Праговата стойност не е критична - тя силно зависи от качеството на генерирания код.
Ако последният израз на функция е извикване на тази функция, се казва, че тя е рекурсивна в опашката. Има смисъл да се замени с итерации - в този случай стекът се използва по-добре. Това се прави при второто извикване наQuickSortна фиг. 2.3.
След разделянето първо се сортира по-малкият дял. Това също води до по-добро използване на стека, тъй като късите секции сортират по-бързо и се нуждаят от по-къс стек.

В раздел 4.4 ще намерите иqsort, функция от стандартната библиотека C, която, както подсказва името, е базирана на алгоритъма за бързо сортиране. За тази реализация рекурсията е заменена с итерация. Таблица 2.1 показва времето и размера на стека преди и след описаните подобрения.