Жылдам сұрыптау алгоритмі

Кіріспе

Бөліп-бөліп шешу алгоритмі

Quicksort – тиімді, жалпы мақсаттағы сұрыптау алгоритмі. Quicksort әдісін 1959 жылы британдық компьютер ғалымы Тони Хоэр әзірлеген және 1961 жылы жариялаған. Ол әлі күнге дейін сұрыптау үшін кеңінен қолданылатын алгоритм болып табылады. Жалпы алғанда, ол кездейсоқ деректер үшін, әсіресе үлкен жиынтарда, біріктіру сұрыптаудан және үймелеу сұрыптаудан сәл жылдам. Quicksort – бұл бөліп-бөліп шешу алгоритмі. Ол массивтен 'тіреу' элементін таңдап, қалған элементтерді тіреутен үлкен немесе кішкентай болуына қарай екі кіші массивке бөлу арқылы жұмыс істейді. Осы себепті ол кейде бөлу және алмастыру сұрыптау деп аталады. Содан кейін кіші массивтер рекурсивті түрде сұрыпталады. Бұл орынды пайдаланып жасауға болады, сұрыптауды орындау үшін аз ғана қосымша жад қажет. Quicksort – салыстыруға негізделген сұрыптау, яғни ол "кішкентай" қатынасы (формалды түрде, толық реттелу) анықталған кез келген типтегі элементтерді сұрыптай алады. Бұл салыстыру негізіндегі сұрыптау, себебі a және b элементтері тек олардың салыстырмалы реті бұрынғы салыстыру нәтижелерінің транзитивті жабылуында анықталған жағдайда ғана алмастырылады. Quicksort-тың көптеген іске асырылымдары тұрақты емес, яғни бірдей сұрыптау элементтерінің салыстырмалы реті сақталмайды. Quicksort-тың математикалық талдауы көрсеткендей, орташа есеп бойынша алгоритм n элементті сұрыптау үшін салыстыруды қажет етеді. Ең нашар жағдайда, ол салыстыру жасайды.

Тарих

Тез сұрыптау алгоритмін 1959 жылы Тони Хоарь Мәскеу мемлекеттік университетінде студент ретінде оқып жүргенде жасады. Сол кезде Хоарь Ұлттық физикалық зертханада машиналық аударма жобасымен айналысып жүрді. Аударма процесінің бір бөлігі ретінде, ол сөздерді орыс тіліндегі сөйлемдерде сұрыптап, содан кейін магниттік таспада сақталған орысша-ағылшынша сөздікте іздеуі керек болды. Оның алғашқы идеясы – енгізу сұрыптау, өте баяу боларын түсінген соң, ол жаңа идеяға келді. Ол бөлу бөлігін Mercury Autocode-та жазды, бірақ сұрыпталмаған сегменттер тізімін басқаруда қиындықтар туды. Англияға оралғаннан кейін, одан Shellsort үшін код жазуды сұрады. Хоарь өзінің бастығына одан жылдам алгоритмді білетінін айтты, ал бастығы оның білмейтініне алты пенс тігіс қойды. Ақырында бастығы тігісті ұтылғанын мойындады. Хоарь өзінің алгоритмі туралы мақаласын The Computer Journal журналының 5-томы, 1-саны, 1962 жылғы 10-16 беттерінде жариялады. Кейін Хоарь ALGOL және оның рекурсия жасау мүмкіндігі туралы білді, бұл оған алгоритмнің жақсартылған нұсқасын сол кездегі ең беделді компьютерлік ғылым журналы – Computing Machinery Association Communications-те ALGOL тілінде жариялауға мүмкіндік берді. ALGOL коды ACM (CACM) журналының 4-томы, 7-шы айы, 1961 жылғы 321-бетте, 63-алгоритм: бөлу және 64-алгоритм: тез сұрыптау ретінде жарияланды. Quicksort кеңінен қолданысқа енді, мысалы, Unix жүйесінде әдепкі кітапхананың сұрыптау ішкі бағдарламасы ретінде пайда болды. Сондықтан ол C стандартты кітапханасының ішкі бағдарламасына, сондай-ақ салыстырулар мен алмасулардың күтілетін санын есептеуге де өз атын берді. Бентли сол эссесінде Quicksort-ты "мен жазған ең әдемі код" деп сипаттады. Ломутоның бөлу схемасы "Алгоритмдерге кіріспе" оқулығында танымал болды, бірақ ол Хоарьдің схемасына қарағанда нашар, себебі ол орташа есеппен үш есе көп алмасу жасайды және барлық элементтер тең болған жағдайда O(n^2) уақытында жұмыс істейді. 1998 жылы Макилрой AntiQuicksort функциясын жасады, ол тіпті 1993 жылғы Quicksort-тың да квадратық мінез-құлыққа түсуіне себеп болды, өйткені ол қарсыластық деректерді дереу жасады.

The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. At that time, Hoare was working on a machine translation project for the National Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian English dictionary, which was in alphabetical order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he came up with a new idea. He wrote the partition part in Mercury Autocode but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for Shellsort. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet a sixpence that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm in The Computer Journal Volume 5, Issue 1, 1962, Pages 10–16. Later, Hoare learned about ALGOL and its ability to do recursion that enabled him to publish an improved version of the algorithm in ALGOL in Communications of the Association for Computing Machinery, the premier computer science journal of the time. The ALGOL code is published in Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort. Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort subroutine. Hence, it lent its name to the C standard library subroutine as well as derivation of expected number of comparisons and swaps. Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbook Introduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to O(n^(2)) runtime when all elements are equal. McIlroy would further produce an AntiQuicksort function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on the fly.

Алгоритм

Quicksort - массивті сұрыптау үшін бөлу және басқару алгоритмінің бір түрі, ол бөлу процедурасына негізделген; осы бөлудің егжей-тегжейі шамалы өзгеруі мүмкін, сондықтан quicksort - бұл шын мәнінде тығыз байланысты алгоритмдер отбасы. Кем дегенде екі элементтен тұратын диапазонға қолданғанда, бөлу екі тікелей, бос емес қосалқы диапазонға бөлінеді, осылайша бірінші қосалқы диапазонның ешбір элементі екінші қосалқы диапазонның кез келген элементінен үлкен болмайды. Осы бөліністен кейін quicksort қосалқы диапазонды рекурсивті түрде сұрыптайды, мүмкін, бөліну нүктесіндегі элементті алып тастағаннан кейін, ол осы сәтте өз соңғы орнында екені белгілі. Рекурсивті табиғатына байланысты quicksort (бөлу процедурасы сияқты) үлкен массивтің ішіндегі диапазон үшін шақырылатындай етіп құрастырылуы керек, тіпті соңғы мақсат толық массивті сұрыптау болса да. Орнында quicksort үшін қадамдар: Егер диапазонның ішінде екі элементтен кем болса, дереу қайта оралыңыз, өйткені ештеңе жасаудың қажеті жоқ. Мүмкін, өте қысқа ұзындықтар үшін арнайы сұрыптау әдісі қолданылады және осы қадамдардың қалғаны жіберіліп қойылады. Әйтпесе, диапазонның ішінде кездесетін півот деп аталатын мәнді таңдаңыз (нақты таңдау әдісі бөлу процедурасына байланысты және кездейсоқтықты қамтуы мүмкін). Диапазонды бөліңіз: элементтерін қайта реттеңіз, сонымен бірге бөліну нүктесін анықтаңыз, осылайша півоттан кіші мәндері бар барлық элементтер бөлінуден бұрын, ал півоттан үлкен мәндері бар барлық элементтер одан кейін орналасады; півотқа тең элементтер екі жаққа да орналаса алады. Півоттың кем дегенде бір мысалы болғандықтан, көптеген бөлу процедуралары бөліну нүктесіндегі мән півотқа тең болады және қазірдің өзінде соңғы орнында болады деп қамтамасыз етеді (бірақ quicksort аяқталуы осыған байланысты емес, егер бастапқыдан кішкентай қосалқы диапазон туындаса). Бөліну нүктесіне дейінгі және одан кейінгі қосалқы диапазонға quicksort-ты рекурсивті түрде қолданыңыз, мүмкін, екі диапазоннан да бөліну нүктесіндегі півотқа тең элементті алып тастаңыз. (Егер бөлу шекараға жақын үлкен қосалқы диапазонды тудырса, онда барлық элементтер півотқа тең деп танылса, оларды да алып тастауға болады.) Бөлу процедурасын таңдау (оның ішінде півотты таңдау) және жоғарыда толық көрсетілмеген басқа да егжей-тегжейлер алгоритмнің өнімділігіне әсер етуі мүмкін, тіпті белгілі бір кіріс массивтері үшін айтарлықтай. Quicksort-тың тиімділігін талқылау кезінде осы таңдауларды бірінші кезекте нақтылау қажет. Мұнда екі нақты бөлу әдісін атап өтейік.

Quicksort is a type of divide and conquer algorithm for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms. Applied to a range of at least two elements, partitioning produces a division into two consecutive non empty sub ranges, in such a way that no element of the first sub range is greater than any element of the second sub range. After applying this partition, quicksort then recursively sorts the sub ranges, possibly after excluding from them an element at the point of division that is at this point known to be already in its final location. Due to its recursive nature, quicksort (like the partition routine) has to be formulated so as to be callable for a range within a larger array, even if the ultimate goal is to sort a complete array. The steps for in place quicksort are:
If the range has fewer than two elements, return immediately as there is nothing to do. Possibly for other very short lengths a special purpose sorting method is applied and the remainder of these steps skipped. Otherwise pick a value, called a pivot, that occurs in the range (the precise manner of choosing depends on the partition routine, and can involve randomness). Partition the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way. Since at least one instance of the pivot is present, most partition routines ensure that the value that ends up at the point of division is equal to the pivot, and is now in its final position (but termination of quicksort does not depend on this, as long as sub ranges strictly smaller than the original are produced). Recursively apply the quicksort to the sub range up to the point of division and to the sub range after it, possibly excluding from both ranges the element equal to the pivot at the point of division. (If the partition produces a possibly larger sub range near the boundary where all elements are known to be equal to the pivot, these can be excluded as well.) The choice of partition routine (including the pivot selection) and other details not entirely specified above can affect the algorithm's performance, possibly to a great extent for specific input arrays. In discussing the efficiency of quicksort, it is therefore necessary to specify these choices first. Here we mention two specific partition methods.

Параллельдеу

Quicksort-тың бөліп-жеңу қағидасы тапсырмалық параллелизмді пайдалану арқылы оны параллельдеуге қолайлы етеді. Бөлу кезеңі параллель префикс суммасы алгоритмін қолдану арқылы жүзеге асырылады, бұл әрбір массив элементі үшін бөлінген массивінің бөліміндегі индексті есептейді. n өлшемді массив үшін бөлу кезеңі O(n) жұмысты O(log n) уақытында орындайды және O(n) қосымша уақытша жадты қажет етеді. Массив бөлінгеннен кейін екі бөлімді параллель рекурсивті түрде сұрыптауға болады. Півоттардың ең жақсы таңдалуын болғанда, параллель quicksort n өлшемді масситті O(n log n) жұмысты O(log² n) уақытында, O(n) қосымша жадты пайдалана отырып сұрыптайды. Quicksort-тың тиімді параллельдеуін қиындататын, merge sort сияқты балама сұрыптау алгоритмдерімен салыстырғанда кейбір кемшіліктері бар. Quicksort-тың бөліп-жеңу ағашының тереңдігі алгоритмнің кеңейтілуіне тікелей әсер етеді, ал бұл тереңдік алгоритмнің півот таңдауына өте байланысты. Сонымен қатар, бөлу кезеңін тиімді түрде параллельдеу қиын. Уақытша жадты пайдалану бөлу кезеңін жеңілдетеді, бірақ алгоритмнің жад көлемін және тұрақты қосымша шығындарды арттырады. Басқа, күрделі параллель сұрыптау алгоритмдері одан да жақсы уақыт шектеріне қол жеткізе алады. Мысалы, 1991 жылы Дэвид М.В. Пауэрс n процессорлы CRCW (concurrent read and concurrent write) PRAM (параллельді кездейсоқ қолжетімділік машинасы) жүйесінде O(log n) уақытында жұмыс істей алатын параллель quicksort-ты (және оған байланысты radix sort-ты) сипаттады, бұл бөлуді жасырын түрде жүзеге асыру арқылы мүмкін болды.

Ең нашар жағдайды талдау

Ең теңгерімсіз бөлу, бөлшектеу процедурасы қайтаратын кіші тізімдердің бірі n-1 өлшемде болғанда пайда болады. Бұл півот тізімдегі ең кішкентай немесе ең үлкен элемент болғанда, немесе кейбір іске асыруларда (мысалы, жоғарыда сипатталған Lomuto бөлу схемасы) барлық элементтер тең болғанда болуы мүмкін. Егер мұндай жағдай әр бөлу кезінде қайталап орын алса, әр рекурсивті шақыру алдыңғы тізімнен бір элемент кем тізімді өңдейді. Осының салдарынан, 1 өлшемді тізімге жеткенше n-1 деңгейлі шақырулар жасалады. Бұл шақыру ағашы n-1 деңгейлі шақырулардың тізбектік тізбегі екенін білдіреді. I-ші шақыру бөлуді орындау үшін O(n-i) жұмыс атқарады, сондықтан бұл жағдайда жылдам сұрыптау O(n²) уақыт алады.

Ең жақсы жағдайды талдау

Ең теңдестірілген жағдайда, әр бөліс жасағанда тізімді шамамен тең екі бөлікке бөлеміз. Яғни, әрбір рекурсивті шақыру бастапқы тізімнің жартысына дейін қысқартылған тізімді өңдейді. Осылайша, 1 өлшемді тізімге жету үшін біз log2 n рекурсивті шақыру жасай аламыз. Бұл шақыру ағашының тереңдігі log2 n екенін білдіреді. Алайда, шақыру ағашының бір деңгейіндегі екі шақыру бастапқы тізімнің бірдей бөлігін өңдемейді; сондықтан, шақырулардың әрбір деңгейіне барлығы O(n) уақыт жұмсалады (әрбір шақырудың тұрақты шығындары бар, бірақ әр деңгейде тек O(n) шақыру болғандықтан, бұл O(n) факторына сіңіріледі). Соның салдарынан, алгоритм O(n log n) уақытты ғана пайдаланады.

Орташа жағдайды талдау

N түрлі элементтердің массивін сұрыптау үшін жылдам сұрыптау, барлық n! элементтің тең ықтималдығымен болатын пермутациялары бойынша орташа есептегенде O(n log n) уақыт алады. Балама ретінде, егер алгоритм кіріс массивінен півотты біркелкі кездейсоқ түрде таңдаса, кез келген кіріс тізбегі үшін күтілетін жұмыс уақытын шектеу үшін дәл сол талдау қолданылуы мүмкін; күту содан кейін алгоритм жасаған кездейсоқ таңдаулар бойынша есептеледі (Cormen et al., Алгоритмдерге кіріспе).

Жылдам сұрыптау, орнында және тұрақсыз бөлуді пайдаланатын болса, кез келген рекурсивті шақыру жасамас бұрын тек тұрақты қосымша кеңістік ғана қолданады. Жылдам сұрыптау әрбір ішкі рекурсивті шақыру үшін тұрақты көлемде ақпарат сақтауы керек. Ең жақсы жағдайда ең көп дегенде O(log n) ішкі рекурсивті шақыру жасалатындықтан, ол O(log n) кеңістік қолданады. Дегенмен, рекурсивті шақыруларды шектеу үшін Седжвиктің әдісі қолданылмаса, ең жаман жағдайда жылдам сұрыптау O(n) ішкі рекурсивті шақыру жасауы мүмкін және O(n) көмекші кеңістік қажет болады. Биттік күрделілік тұрғысынан алғанда, lo және hi сияқты айнымалылар тұрақты кеңістік қолданбастайды; n элементтен тұратын тізімге индекстеу үшін O(log n) бит қажет. Әрбір стек кадрында мұндай айнымалылар болғандықтан, Седжвиктің әдісін қолданатын жылдам сұрыптау O((log n)^2) бит кеңістік қажет етеді. Бұл кеңістік талабы тым үлкен емес, себебі тізімде ерекше элементтер болса, оған кем дегенде O(n log n) бит кеңістік қажет болар еді. Басқа, сирек қолданылатын, орнында емес жылдам сұрыптау нұсқасы жұмыс сақтау үшін O(n) кеңістік қолданады және тұрақты сұрыптауды іске асыруы мүмкін. Жұмыс сақтау кіріс массивін тұрақты түрде оңай бөлуге және содан кейін рекурсивті шақырулар үшін кіріс массивіне көшіруге мүмкіндік береді. Седжвиктің оптимизациясы әлі де тиімді.

Басқа алгоритмдермен байланысы

Quicksort – бинарлық ағаш сұрыптауының жадты үнемдеуге бағытталған нұсқасы. Анық ағашқа элементтерді тізбектей енгізудің орнына, quicksort оларды рекурсивті шақырулар арқылы көрінетін ағашта бірден ұйымдастырады. Алгоритмдер дәл сол салыстыруларды жасайды, бірақ басқа ретпен. Сорттау алгоритмінің маңызды қасиеттерінің бірі – тұрақтылық, яғни салыстыру нәтижесі тең элементтердің реті өзгереді, бұл көп кілтті кестелердің (мысалы, каталогтар немесе папкалар тізімі) реттілігін табиғи түрде басқаруға мүмкіндік береді. Орындалатын quicksort үшін бұл қасиетті сақтау қиын (ол тек тұрақты қосымша жадыны сілтемелер мен буферлер үшін және O(log n) қосымша жадыны ашық немесе жасырын рекурсияны басқару үшін пайдаланады). Көрнекілеуге (мысалы, тізімдер немесе ағаштар) немесе файлдарға (фактылық түрде тізімдер) байланысты қосымша жадыны қажет ететін quicksort нұсқалары үшін тұрақтылықты сақтау оңай. Құрылымдар неғұрлым күрделі немесе дискіге байланысты болса, уақыт шығындары артады, әдетте виртуалды жад немесе дискіні көбірек пайдаланады. Quicksort-тың тікелей бәсекелесі – heapsort. Heapsort қарапайымдылығымен және ең жаман жағдайда O(n log n) орындалу уақытымен артықшылықтарға ие, бірақ heapsort-тың орташа орындалу уақыты әдетте орындалатын quicksort-тан баяу деп есептеледі, негізінен нашар сілтемелік жеріне байланысты. Бұл нәтиже күмәнді; кейбір жарияланымдар керісін көрсетеді. Quicksort-тың басты кемшілігі – жаман півот таңдауларынан және оның салдарынан аулақ болу үшін қажетті күрделі іске асыру. Introsort – quicksort-тың нұсқасы, ол жаман жағдай анықталғанда heapsort-қа ауысу арқылы бұл мәселені шешеді. Басты бағдарламалау тілдері, мысалы C++ (GNU және LLVM нұсқаларында), introsort-ты пайдаланады. 1999 жылғы процессор кэшін тиімді пайдалану үшін баптаудан өткен, півоттардың өзгермелі саны бар multiquicksort бағалауы нұсқаулар санын шамамен 20%-ға арттырды, бірақ симуляция нәтижелері өте үлкен кірістерде тиімдірек болатынын көрсетті. 2009 жылы Ярославский жасаған екі півотты quicksort нұсқасы Java 7-де примитивтер массивін сұрыптаудың стандартты алгоритмі ретінде іске асыруға жеткілікті жылдам болды (объекттер массивін сұрыптау Timsort арқылы жүзеге асырылады). Бұл алгоритмнің өнімділік артықшылығы көбінесе кэш өнімділігімен байланысты екені анықталды, ал тәжірибелік нәтижелер үш півотты нұсқаның қазіргі заманғы машиналарда одан да жақсы жұмыс істеуі мүмкін екенін көрсетеді.

Quicksort is a space optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order. An often desirable property of a sorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e. g. directory or folder listings) in a natural way. This property is hard to maintain for in place quicksort (that uses only constant additional space for pointers and buffers, and O(log n) additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e. g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk. The most direct competitor of quicksort is heapsort. Heapsort has the advantages of simplicity, and a worst case run time of O(n log n), but heapsort's average running time is usually considered slower than in place quicksort, primarily due to its worse locality of reference. This result is debatable; some publications indicate the opposite. The main disadvantage of quicksort is the implementation complexity required to avoid bad pivot choices and the resultant performance. Introsort is a variant of quicksort which solves this problem by switching to heapsort when a bad case is detected. Major programming languages, such as C++ (in the GNU and LLVM implementations), use introsort. A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs. A version of dual pivot quicksort developed by Yaroslavskiy in 2009 turned out to be fast enough to warrant implementation in Java 7, as the standard algorithm to sort arrays of primitives (sorting arrays of objects is done using Timsort). The performance benefit of this algorithm was subsequently found to be mostly related to cache performance, and experimental results indicate that the three pivot variant may perform even better on modern machines.

Сыртқы жылдам сұрыптау

Дискілік файлдар үшін, жылдам сұрыптауға ұқсас бөлуге негізделген сыртқы сұрыптау мүмкін. Бұл сыртқы біріктіру сұрыптаудан баяу, бірақ қосымша дискілік кеңістік қажет етпейді. 4 буфер қолданылады, 2 кіріс үшін, 2 шығыс үшін. N – файлдағы жазбалардың саны, B – буфердегі жазбалардың саны және M = N/B – файлдағы буфер сегменттерінің саны болсын. Деректер файлдың екі шетінен де ішке қарай оқылады (жазылады). X – файлдың басында басталатын сегменттерді, ал Y – файлдың соңында басталатын сегменттерді білдірсін. Деректер X және Y оқу буферлеріне оқылады. Бір півоттық жазба таңдалады және X және Y буферлеріндегі півоттық жазбадан басқа жазбалар півоттық жазбамен салыстырылып, X жазу буферіне өсу ретімен, ал Y жазу буферіне кему ретімен көшіріледі. X немесе Y буфері толтырылғаннан кейін, ол файлға жазылады және келесі X немесе Y буфері файлдан оқылады. Процесс барлық сегменттер оқылып, бір жазу буфері қалғанға дейін жалғасады. Егер бұл буфер X жазу буфері болса, півоттық жазба оған қосылады және X буфері жазылады. Егер бұл буфер Y жазу буфері болса, півоттық жазба Y буферіне қосылады және Y буфері жазылады. Бұл файлды бөлудің бір қадамы болып табылады, және файл енді екі кіші файлдан тұрады. Әрбір кіші файлдың бастапқы және соңғы орналасуы жеке стекке немесе рекурсия арқылы негізгі стекке түртіледі/алынып тасталады. Стекке арналған орынды O(log2(n)) дейін шектеу үшін, кіші кіші файл алдымен өңделеді. Жеке стек үшін, үлкен кіші файлдың параметрлерін стекке түртіңіз, содан кейін кіші кіші файл бойынша итерация жасаңыз. Рекурсия үшін, алдымен кіші кіші файл бойынша рекурсия жасаңыз, содан кейін үлкен кіші файлды өңдеу үшін итерация жасаңыз. Кіші файл 4B жазбадан кем немесе тең болғаннан кейін, кіші файл жылдам сұрыптау арқылы орнында сұрыпталады және жазылады. Бұл кіші файл енді сұрыпталған және файлда орналасқан. Процесс барлық кіші файлдар сұрыпталғанша және орнында тұрғанша жалғасады. Файлдағы өтулердің орташа саны шамамен 1 + ln(N+1)/(4B) құрайды, бірақ ең нашар жағдайдағы үлгі N өту (ішкі сұрыптау үшін O(n^2) тең).

For disk files, an external sort based on partitioning similar to quicksort is possible. It is slower than external merge sort, but doesn't require extra disk space. 4 buffers are used, 2 for input, 2 for output. Let N = number of records in the file, B = the number of records per buffer, and M = N/B = the number of buffer segments in the file. Data is read (and written) from both ends of the file inwards. Let X represent the segments that start at the beginning of the file and Y represent segments that start at the end of the file. Data is read into the X and Y read buffers. A pivot record is chosen and the records in the X and Y buffers other than the pivot record are copied to the X write buffer in ascending order and Y write buffer in descending order based comparison with the pivot record. Once either X or Y buffer is filled, it is written to the file and the next X or Y buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an X write buffer, the pivot record is appended to it and the X buffer written. If that buffer is a Y write buffer, the pivot record is prepended to the Y buffer and the Y buffer written. This constitutes one partition step of the file, and the file is now composed of two subfiles. The start and end positions of each subfile are pushed/popped to a stand alone stack or the main stack via recursion. To limit stack space to O(log2(n)), the smaller subfile is processed first. For a stand alone stack, push the larger subfile parameters onto the stack, iterate on the smaller subfile. For recursion, recurse on the smaller subfile first, then iterate to handle the larger subfile. Once a sub file is less than or equal to 4 B records, the subfile is sorted in place via quicksort and written. That subfile is now sorted and in place in the file. The process is continued until all sub files are sorted and in place. The average number of passes on the file is approximately 1 + ln(N+1)/(4 B), but worst case pattern is N passes (equivalent to O(n^2) for worst case internal sort).

Үш жолды радикс жылдам сұрыптау

Бұл алгоритм радикстік сұрыптау мен жылдам сұрыптаудың комбинациясы болып табылады. Массивтен элементті (пивотты) таңдап, жолдың бірінші таңбасын (кілт) қарастырыңыз (көп кілтті). Қалған элементтерді үш жиынға бөліңіз: сәйкес таңбасы пивоттың таңбасынан кішкентай, тең және үлкен элементтер. "Кішкентай" және "үлкен" жиындарды бір таңба бойынша рекурсивті түрде сұрыптаңыз. "Тең" жиынды келесі таңба (кілт) бойынша рекурсивті түрде сұрыптаңыз. Егер біз байттарды немесе W битті сөздер арқылы сұрыптасақ, ең жақсы жағдай O(KN) және ең нашар жағдай O(2^KN) немесе кем дегенде O(N^2) болады, стандартты жылдам сұрыптау сияқты, бірегей кілттер үшін N<2^K болғанда, ал K – барлық стандартты салыстыру сұрыптау алгоритмдеріндегі, оның ішінде жылдам сұрыптаудағы жасырын тұрақты шама. Бұл үш жолды жылдам сұрыптаудың бір түрі, онда ортаңғы жиын пивотқа дәл тең элементтердің (тривиальды) сұрыпталған кіші массивін көрсетеді.

Тез радикс сұрыптау

Сондай-ақ, Пауэрс бұл мәселені O(K) параллель PRAM алгоритмі ретінде әзірледі. Бұл, қайтадан, радикстік сұрыптау мен жылдам сұрыптаудың комбинациясы, бірақ жылдам сұрыптаудың солға/оңға бөлу шешімі кілттің тізбектелген биттері бойынша жасалады, сондықтан N K биттік кілттер үшін O(KN) болады. Барлық салыстыруға негіделген сұрыптау алгоритмдері K-ның Θ(log N) мәнімен трансдихотомиялық модельді түсіндіреді, өйткені K кішірек болса, хэш-кесте немесе бүтін сандық сұрыптауды қолдану арқылы O(N) уақытында сұрыптауға болады. Егер K ≫ log N болса, бірақ элементтер O(log N) биттерінің ішінде бірегей болса, қалған биттер жылдам сұрыптау немесе жылдам радикстік сұрыптау кезінде қарастырылмайды. Әйтпесе, барлық салыстыруға негіделген сұрыптау алгоритмдері де O(K) салыстырмалы түрде тиімсіз биттерді қарауға бірдей жүктеледі, бірақ жылдам радикстік сұрыптау стандартты жылдам сұрыптау мен радикстік жылдам сұрыптаудың ең нашар жағдайдағы O(N^(2)) мінез-құлқынан аулақ болады және осы uniqueprefix(K) ≫ log N шарттарында тіпті осы салыстыру алгоритмдерінің ең жақсы жағдайында да жылдам болады. Салыстыру, радикстік және параллель сұрыптаудың жасырын жүктемелері туралы толық ақпарат алу үшін Пауэрстің еңбектерін қараңыз.

BlockQuicksort (Блокты тез сұрыптау)

Кез келген салыстыруға негізделген сұрыптау алгоритмінде салыстыру санын азайту үшін әр салыстырудан алынатын ақпарат көлемін барынша арттыру қажет, яғни салыстыру нәтижелері болжамсыз болуы тиіс. Бұл жиі тармақтардың дұрыс болжалданбауына (branch mispredictions) әкеледі, бұл өнімділікті шектейді. BlockQuicksort жылдам сұрыптаудың есептеулерін қайта құрылымдап, болжамсыз тармақтарды деректерге тәуелділікке айналдырады. Бөлу кезінде кіріс орташа мөлшердегі блоктарға бөлінеді (олар деректер кэшіне оңай сыйып қана қоймай, тиімді пайдаланылады), және екі массив алмастырылатын элементтердің орналасуымен толтырылады. (Шартты тармақтарды болдырмау үшін, орналасу массивтің соңына шартсыз сақталады, ал алмастыру қажет болған жағдайда, соңғы индекс бірге өсіріледі.) Екінші кезеңде массивтерде көрсетілген орналасулардағы элементтер алмастырылады. Екі циклдың да тек бір шартты тармағы бар – тоқтау тесті, ол көбінесе орындалады. BlockQuicksort әдісі LLVM-нің C++ STL реализациясына, libcxx-ке енгізілді, бұл кездейсоқ бүтін сандар тізбегі үшін 50%-ға дейін өнімділікті арттырады. Үлгіні жеңіп шығатын жылдам сұрыптау (pdqsort), introsort-тың бір түрі, де осы техниканы қолданады.

Ішінара және қосымша жылдам сұрыптау

Көптеген жылдам сұрыптау нұсқалары бар, олар кірістің қалған бөлігінен ең кішкентай немесе ең үлкен k элементін бөліп шығарады.

Жалпылау

Ричард Коул мен Дэвид К. Кандатил 2004 жылы бір параметрлі реттеу алгоритмдерінің отбасын ашты, олар бөліс реттеулер деп аталды. Олардың орташа көрсеткіші (барлық кіріс тізбектерінің ықтималдығы бірдей болғанда) ең көп салыстыру (ақпараттық-теориялық ең төменгі шекке жуық) және операция жасайды; ең жаман жағдайда олар салыстыру (және операция) жасайды. Бұл алгоритмдер қосымша жадты қажет етпейтін, орнында жұмыс істейтін түрі. Оптимизацияланған жылдам реттеулермен (Sedgewick және Bentley McIlroy) салыстырғанда, олардың тиімділігі жоғары және өнімділік ауытқулары аз екені көрсетілді.