Подобрени алгоритми за сортиране
Всички алгоритми, разгледани в предишните раздели, имат един фатален недостатък - времето им за изпълнение е от порядъка на n 2 . Това прави сортирането на големи количества данни много бавно. Като такива, в един момент тези алгоритми стават твърде бавни, за да бъдат приложени [1] . За съжаление, историите на ужасите за „видове, продължили три дни“ често са реални. Когато сортирането отнема твърде много време, това обикновено се дължи на неефективността на използвания в него алгоритъм. Въпреки това, първата реакция в такава ситуация често е ръчно оптимизиране на кода, може би чрез пренаписване на асемблер. Въпреки че ръчната оптимизация понякога ускорява процедурата с постоянен фактор [2] , ако алгоритъмът за сортиране не е ефективен, сортирането винаги ще бъде бавно, без значение колко оптимално е написан кодът. Трябва да се помни, че ако времето за изпълнение на процедурата е пропорционално на n 2 , тогава увеличаването на скоростта на кода или компютъра ще даде само малко подобрение [3] , тъй като времето за изпълнение се увеличава с n 2 . (Всъщност крива n 2 на фигура 21.1 (балонно сортиране) се простира надясно, но иначе е вярна.) Има правило, че ако алгоритъмът, използван в дадена програма, е твърде бавен сам по себе си, никаква ръчна оптимизация няма да направи програмата достатъчно бърза. Решението е да се приложи по-добър алгоритъм за сортиране.
По-долу са описани два отлични метода за сортиране. Първият се нарича Shell sort. Вторият, бързо сортиране, обикновено се счита за най-добрият алгоритъм за сортиране. И двата метода са по-усъвършенствани методи за сортиране и имат много по-добра цялостна производителност от който и да е от простите методи по-горе.
Сортиране на черупки
Ориз. 21.2. Сортиране на черупки
Че този метод дава добри резултати или дори че сортира масива изобщо, не е толкова лесно да се види. Това обаче е вярно. Всеки проход за сортиране покрива сравнително малък брой елементи или елементи, които вече са в относителен ред. Следователно Shellsort е ефективен и всяко преминаване увеличава реда [6] .
Конкретната последователност от стъпки може да е различна. Единственото правило е, че последната стъпка е 1. Например тази последователност:
дава добри резултати и се използва при изпълнението на Shellsort, показано тук. Последователностите, които са степени на 2, трябва да се избягват - поради математически сложни причини те намаляват ефективността на сортирането (но сортирането все още работи!).
Може би сте забелязали, че вътрешният for цикъл има две тестови условия. Очевидно сравнението x е необходимо за процеса на сортиране. Изразът j>=0 предотвратява излизането на масива от елементи извън границите. Тези допълнителни проверки влошават производителността на Shellsort до известна степен.
Леко модифицирани версии на този метод за сортиране използват специални елементи от масив, наречени сигнални етикети. Те не принадлежат към самия сортируем масив, но съдържат специални стойности, съответстващи на възможно най-малките и най-големите възможни елементи [7] . Това елиминира необходимостта от проверка за масив извън границите. Въпреки това, използването на етикети на реплики на елементи изисква специфична информация за данните, които трябва да бъдат сортирани, което намалява общото съдържание на функцията за сортиране.
Shellort анализът включва много сложни математически проблеми, които отиват далеч отвъдтази книга. Приемете за даденост, че времето за сортиране е пропорционално
при сортиране на n елемента [8] . И това вече е значително подобрение спрямо сортирането от ред n 2 . За да разберете колко е голям, вижте фиг. 21.3, който показва графики на функциите n 2 и n 1.2. Въпреки това, не се вълнувайте твърде много от Shellsort - quicksort е още по-добър.
Ориз. 21.3. Опит за визуализиране на кривите n 2 и n 1,2. Въпреки че не е възможно да начертаете тези криви с точен мащаб на който и да е значителен интервал за целите на сортирането на броя записи (n), например в интервала от 0 до 1000, можете да получите представа за поведението на тези криви, като използвате графиките на функциите y=(n/100) 2 и y=(n/100) 1.2. За сравнение се изгражда и графика на правата линия y \u003d n / 100. Освен това, за да получите представа за растежа на тези криви, можете да вземете логаритмична скала на оста y - това е същото като да начертаете логаритмите на тези функции
Бързо сортиране
Quicksort, измислен и кръстен на Чарлз Антъни Ричард Хоаре [9], е най-добрият метод за сортиране, представен в тази книга и обикновено се счита за най-добрия алгоритъм за сортиране с общо предназначение, който съществува в момента. Базира се на обменно сортиране - изненадващ факт, като се има предвид ужасното представяне на балонното сортиране!
Quicksort е изграден върху идеята за разделяне. Общата процедура е да изберете някаква стойност, наречена comparand [10] и след това да разделите масива на две части. Всички елементи, по-големи или равни на компаранда, се преместват на едната страна, а тези, които са по-малки от компаранда, се преместват в другата. След това този процес се повтаря завсяка част, докато масивът бъде сортиран. Например, ако оригиналният масив се състои от знаците fedacb и символът d се използва като компаранд, първото преминаване на бързото сортиране ще пренареди масива, както следва:
След това сортирането се повтаря и за двете половини на масива, т.е. bca и def. Както можете да видите, този процес по своята същност е рекурсивен и наистина, в най-чистата си форма, бързото сортиране е имплементирано като рекурсивна функция [11] .
Сравнителната стойност може да бъде избрана по два начина - произволно или чрез осредняване на малък брой стойности от масив. За оптимално сортиране трябва да изберете стойност, която се намира точно в средата на диапазона от всички стойности. Това обаче не е лесно да се направи за повечето набори от данни. В най-лошия случай избраната стойност е една от крайностите. Но дори и в този случай бързото сортиране работи правилно. Следващата версия на бързото сортиране избира средния елемент на масива като компаранд.
В тази версия функцията quick() подготвя извикване към основната функция за сортиране qs(). Това осигурява общ интерфейс с елементите и параметрите за броене, но не е от съществено значение, тъй като можете да извикате функцията qs() директно с три аргумента.
Получаването на броя сравнения и суапове, които бързото сортиране извършва, изисква математически изчисления, които са извън обхвата на тази книга. Средният брой сравнения обаче е
а средният брой обмени е приблизително равен на
Тези стойности са много по-малки от съответните характеристики на алгоритмите за сортиране, разгледани по-рано.
Трябва да се спомене един особено проблематичен аспект на бързото сортиране. Ако сравнителната стойност във всяко деление е равна на най-голяматастойност, бързото сортиране става "бавно сортиране" с време на изпълнение от порядък n 2 . Затова внимателно изберете метода за определяне на компаранда. Този метод често се определя от естеството на данните, които се сортират. Например при много големи пощенски списъци, които са сортирани по пощенски код, изборът е лесен, тъй като пощенските кодове са сравнително равномерно разпределени – сравнението може да се определи с помощта на проста алгебрична функция. В други бази данни обаче случайната стойност често е най-добрият избор. Популярен и доста ефективен метод е да изберете три елемента от частта от масива, която трябва да се сортира, и да вземете за сравнение стойността, разположена между другите две.
[1] Разбира се, това не означава, че функцията f(n)=n 2 в даден момент нараства рязко. Въобще не! Просто когато размерът на масива n се увеличи, естеството на сортирането се променя, от вътрешно всъщност става външно, когато масивът не се побира в RAM и започва интензивно страниране, последвано от приплъзване на механизма на виртуалната памет. Тези събития наистина могат да дойдат внезапно и тогава може да изглежда, че леко увеличаване на сортирания масив или просто добавяне на някаква напълно незначителна задача ще доведе до катастрофално увеличаване на времето за сортиране (например десетки пъти!).
[3] Действително, за да се увеличи размерът на сортирания масив с m пъти при запазване на времето за сортиране, скоростта на процесора ще трябва да се увеличи с m 2 пъти, при условие че времето за достъп до елементите на масива не се увеличава, т.е. няма да намали, например, ефективността на пейджинг.
[5] Стъпка - разстоянието между сортираните елементи на определен етап от сортирането.
[6] Т.е.намалява броя на смущенията (инверсиите).
[8] Най-общо казано, времето за сортиране на Shell зависи от последователността от стъпки. (Въпреки това, минимумът е, разбира се, n log 2 n .) Оптималната последователност все още е неизвестна. Доналд Кнут изследва различни последователности (без да забравя последователността на Фибоначи). Всъщност той стигна до извода, че има някаква „магия“ в определянето на най-добрата последователност. През 1969 г. Вон Прат открива, че ако всички стъпки са избрани от набор от числа от формата 2 p 3 q по-малко от n, тогава времето за изпълнение ще бъде от порядъка на n(log n) 2 . А.А. Папернов и Г.В. Стасевич през 1965 г. доказва, че максималното време на сортиране на Shell не надвишава O(n 1.5) и е невъзможно да се намали експонентата 1.5. Голям брой експерименти с Shellsort бяха проведени от Джеймс Питърсън и Дейвид Л. Ръсел в Станфордския университет през 1971 г. Те се опитаха да определят средния брой ходове при 100 ≤ n ≤ 250`000 за последователност от стъпки от 2 k -1. Най-подходящите формули се оказаха 1.21 n 1.26 и .39 n (ln n) -2.33 n ln n . Но при промяна на обхвата на n се оказа, че коефициентите в представянето на степенната функция практически не се променят, докато коефициентите в логаритмичното представяне се променят доста рязко. Следователно е естествено да се предположи, че степенната функция е тази, която описва истинското асимптотично поведение на Shellsort.
[9] Съществува и изписването C. E. R. Hoor.
[10] Comparand е операнд в операция за сравнение. Понякога се нарича също основа и критерий за разделяне.
[11] Ако искате да избегнете рекурсия, не се притеснявайте, всичко е много лесно за пренаписване дори за Fortran IV, в литературата, спомената по-рано, можете лесно да намерите желаната нерекурсивна опция.