Сортиране на данни в масива

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

Сортиране вложки

Вмъкването вид е подобен на процеса на размесването на картите с имената. Секретар поставя всяко име на картата, а след това подрежда картите по азбучен ред, като поставите картата в горната част на комина на правилното място. Нека да опише този процес в нашия пример списък петорен А = 50, 20, 40, 75, 35 (фигура 1).

Изчислителната ефективността на сортиране вложки

Сортиране вложки изисква определен брой карти. От N-1 елементи са вмъкнати в пасажи на А [1] до А [М-1]. На-тото прохода на вложката са произведени в подсписък А [0] -А [Ь] и изисква средно I / 2 сравнения. Общ брой на сравнения, равни на

За разлика от други методи, не използва за сортиране вложки борси. Сложността на алгоритъма се измерва и броят на сравнения е равна О (N2). Най-добър случай - когато списъка на източниците вече е сортиран. След това, по-тото прохода на вложката се произвежда в точката А [I], и общия брой на сравнения е равно на п-1, т.е. сложност е О (п). В най-лошия случай е налице, когато списъкът се сортира в низходящ ред. Тогава всеки вмъкване настъпва в точка А [0] и и изисква сравнения. Общ брой сравнения е равно на п (п-1) / 2, т.е. сложност е О (N2).

"Fast" за сортиране

Така че, ние погледна сортиране алгоритъм масив има сложност на ред O (n2). Алгоритми, които използват дървета (сортиране турнир, сортиране по дървото за търсене), осигуряват значително по-добра производителност O (п log2n). Въпреки факта, че те се нуждаят от копие на масива в дърво и обратно, тези разходи са за сметка на по-голяма ефективност на самата сортиране.

Широко използван метод пирамидално сортиране също третира масива "ин ситу" и има ефективност на О (п log2n). Въпреки това, "постът" сортиране, който е изобретен K.Hoar, за повечето приложения, надвишава пирамидално сортиране и е най-бързият известните до сега.

Описание на "бърза" сортирането

Както при повечето алгоритми за сортиране, методи за "бързо" нещо, взети от всекидневния опит. За да сортирате голяма купчина азбука карти по име, може да се раздели на две по-малки стакове по отношение на някои букви, като например К. имена по-малък или равен на K, отидете в една купчина, а другият - от другата.

След това всяка купчина отново разделена на две. Например, на фигура 2 преградните точки са буквите F и R. Метод за разделяне на по-малки и по-малки стека продължава.

Алгоритъмът на "бърза" сортиране метода на разделяне се прилага за определяне на централния елемент. Тъй като ние не можем да си позволим да се хвърлят куп забавни около масата като азбучен сортиране на карти, елементите са разделени на групи в рамките на масива. Помислете алгоритъм "бърза" сортиране например, и след това да обсъдят техническите подробности. Да предположим, че са ни дадени масив от 10 числа:

сканиране фаза

Оригиналност "бърза" сортиране се състои в реакция по два показателя през списъка за сканиране. индекс scanUp придвижва нагоре в списъка, и scanDown - надолу. Ние насърчаваме scanUp напред търси елемент на A [scanUp] по-голям от централата. В този момент, сканирането спира, а ние се готвят да преместите елемента намерите в горния под-списък. Преди това движение ще се случи, ние насърчаване Index scanDown надолу в списъка и да намерите елемент на по-малка или равна на централната. По този начин, ние имаме два елемента, които не са в подраздели, и могат да се разменят.

Този процес продължава докато scanUp и не scanDown ще падне един за друг (scanUp = 6, scanDown = 5). В този момент се появи в scanDown подсписък, чиито елементи са по-малко или равно на централната. Стигнахме до точката на разделяне на двата списъка и отбеляза, крайната позиция на централния елемент. В нашия пример размени номера 600 и 450, 800 и 350, 650 и 400 (виж. Фигура 4).

Тогава обмен стойност на централния елемент [0] на А [scanDown]:

Като резултат, ние виждаме две подсписък А [0] - А [5] и А [6] - А [9], където всички елементи на първата подсписък втори малко елементи, а последният елемент на първия подсписък е най-големият му елемент. Така, можем да предположим, че след направено подсписъци операции разделени елемент [5] = 550 (фигура 5). Ако сега ние се справи със суб-списъка на всеки поотделно, а след това ще получите напълно сортиран масив. Имайте предвид, че в действителност и двете под-списък са едно и също масива като оригинала, така че е възможно да се приложи същия алгоритъм. Използвайте същия алгоритъм за масива на части, се нарича рекурсивна фаза.

рекурсивни фаза

Един и същ метод, две обработени под-списък: Sl (А [0] - А [4]) и Sh (А [6] - А [9]). Елемент не трябва да се лечение на [5], тъй като тя вече е на място.

Аналогично се прилага към всеки подсписък, разделяне на под-списъци на по-малки парчета, докато подсписък няма да остане един елемент или докато подсписък е празна.

алгоритъм бързасортировка

Това рекурсивен алгоритъм разделя списък [ниско] - А [високо] на централния елемент, който е избран от средата на списъка

След смяна на централния елемент с А [ниско], първоначалните стойности са дадени индекси scanUp = ниско + 1 и scanDown = високо, посочва началото и в края на списъка, съответно. Алгоритъмът контролира тези два показателя. Първо scanUp се движи нагоре в списъка, докато той надвишава scanDown или до по-голям елемент, отколкото в центъра.

След позициониране scanUp scanDown индекс се движи надолу в списъка, докато не се сблъсква с един елемент по-малка или равна на централната.

Размяна елемент се прекратява, когато scanDown става по-малка, отколкото scanUp. В този момент показва, началото scanDown лявата подсписък, който включва по-малка или равна на основните елементи. scanDown индекс става основна част. Mark централен елемент на А [ниско]:

За лечението на под-списъци с помощта на рекурсия. След откриване на точката на разделяне ние наричаме рекурсивно бързасортировка параметри с нисък, среден и 1 средата + 1, високи. състояние спирка се случва, когато подсписък е по-малко от два елемента, като лъжливо или празен масив, не е необходимо да се организира.

Изчислителната сложност на "бърза" сортирането

Общият анализ на ефективността на "бърза" сортиране е достатъчно трудно. Би било по-добре да се покаже своята изчислителна сложност, отчитане на броя на сравненията за някои идеални предположения. Да приемем, че п - мощност на две, п = 2 к (к = log2 N) и централен елемент се намира точно в средата на всеки списък и да го разделя на две приблизително еднаква дължина подсписък.

Първият сканирането се извършва N-1 сравнения. Това създава две подсписък размер от п / 2. В следващия етап на обработка на всеки подсписък изисква приблизително N / 2 сравнения. Общ брой сравнения в тази фаза е равна на 2 (п / 2) = N. Следващата фаза четири подсписъци се обработват, което изисква 4 (N / 4) сравнения и т.н. В края на процеса на разделяне се прекратява след к преминава когато получените подсписъци съдържат един елемент. Общ брой на сравнения се равнява приблизително

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

Ако масивът е сортиран в низходящ ред, а след това на първо преминаване през централен елемент се намира в средата на списъка и се замениха с всеки елемент от двете първи и втори подсписък. Получената списъка на сортиран почти алгоритъм има сложност на ред О (N log2 N).

Най-лошият сценарий за "бързо" сортиране ще бъде тази, в която основен елемент на всички времена попада в подсписък Сингълтън, както и всички други елементи остават във втората подсписък. Това се случва, когато центърът винаги е най-малкият елемент. Да разгледаме последователност на 3, 8, 1, 5, 9.

На първия проход е п сравнения и повече подсписък съдържа N-1 елементи. На следващия прохода, този подсписък изисква N-1 и осигурява сравнения подсписък на N-2 елементи, и т.н. Общият брой на сравненията е:

В най-лошия случай сложност е О (N 2), т.е. не по-добре от сортиране вложки и избор. Въпреки това, този случай е патологичен и е малко вероятно на практика. Като цяло, средните резултати на първите "бърза" окачествяване-висока от тази счита от нас всички видове.

Бързасортировка алгоритъм е избран като основа на най-разнообразни инструменти за сортиране. Ако не можете да влезе в съответствие с изпълнението на най-лошия случай, използвайте пирамидално сортиране - по-стабилна алгоритъм, чиято сложност е O (N log2 N) и зависи само от размера на списъка.

Сравняване на масиви алгоритми за сортиране

Като цяло бързасортировка е най-бързият алгоритъм. Поради своята ефективност, равна на O (п log2n), то е ясно превъзхожда всички алгоритъм на ред O (N 2). Ако се съди по резултатите от тестовете, изброени в таблицата по-долу, също така е по-бързо от който и да е от реда на подреждане на O (N log2 N), ние сме обсъждали в последния брой. Моля, имайте предвид, че ефективността на "бърза" сортирането е O (N log2 N), дори и в екстремни случаи. Но сортиране по дървото за търсене в тези случаи става О комплекс (N2), оформено като дървото е дегенерат.

Сортиране по дърво

Фиг.8 Сравнение сортиране за О (п log2n)

Сравнение на всевъзможни

Тази програма извършва сравнение на алгоритми за сортиране, данните, представени на фигури 7 и 8. Тук представяме само основната структура на програмата. Времето TickCount извършва с помощта на функция, която връща броя на 1/60 части от секунди, изминали от началото на програмата.