Тізімдерді реттеу алгоритмдері

Кіріспе

Тізімдерді реттеуге арналған алгоритм

Компьютерлік ғылымда сұрыптау алгоритмі – тізім элементтерін белгілі бір ретпен орналастыратын алгоритм. Көбінесе қолданылатын реттер – сандық рет және лексикографиялық рет, өсу реті немесе кему реті. Тиімді сұрыптау, кіріс деректері сұрыпталған тізім түрінде болуын талап ететін басқа алгоритмдердің (мысалы, іздеу және біріктіру алгоритмдері) тиімділігін арттыру үшін маңызды. Сұрыптау деректерді каноникалық түрге келтіру және адамға оңай оқылатын нәтиже алу үшін де жиі қолданылады. Формальды түрде, кез келген сұрыптау алгоритмінің нәтижесі екі шартты орындауы керек:
Нәтиже монотонды ретте болуы тиіс (әр элемент, қажетті ретке сәйкес, алдыңғы элементтен кіші немесе үлкен болмайды). Нәтиже – кіріс деректердің өзгеруі (қайта реттелу, бірақ бастапқы элементтердің барлығы сақталады). Оптималды тиімділік үшін кіріс деректері реттік қолжеткізуге ғана емес, сондай-ақ кездейсоқ қолжеткізуге мүмкіндік беретін деректер құрылымында сақталуы керек.

Тарих және ұғымдар

Компьютерлік есептеулердің бастапқы кезеңдерінен бері сұрыптау мәселесі көптеген зерттеулерге тартты, мүмкін, оның себебі – қарапайым және таныс тұжырымдамасына қарамастан, тиімді шешудің қиындығында. 1951 жыл шамасындағы алғашқы сұрыптау алгоритмдерінің авторларының бірі Бетти Холбертон болды, ол ENIAC және UNIVAC машиналарында жұмыс істеді. Көпіршік сұрыптау (Bubble sort) 1956 жылдан бері талданып келеді. Асимптотикалық тұрғыдан оңтайлы алгоритмдер 20 ғасырдың ортасынан белгілі, ал жаңа алгоритмдер әлі де жасалып жатыр. Көп қолданылатын Timsort алгоритмі 2002 жылы, ал кітапханалық сұрыптау (library sort) 2006 жылы алғаш рет жарияланды. Салыстыру негізінде жұмыс істейтін сұрыптау алгоритмдеріне Ω(n log n) салыстыру қажет (кейбір дерек тізбектеріне n log n салыстырудың еселігі қажет болуы мүмкін, мұнда n – сұрыпталатын массивтегі элементтер саны). Салыстыруға негізделмеген алгоритмдер, мысалы, санау сұрыптау (counting sort), жақсы нәтижелер бере алады. Сұрыптау алгоритмдері компьютерлік ғылымның кіріспе курстарында кеңінен қолданылады, себебі бұл мәселе үшін жасалған көптеген алгоритмдер негізгі алгоритмдік ұғымдармен таныстыруға мүмкіндік береді, мысалы, үлкен O белгісі (big O notation), «бөліп жеңе» алгоритмдері (divide and conquer algorithms), үйірмелер (heaps) және екілік ағаштар (binary trees) сияқты дерек құрылымдары, кездейсоқ алгоритмдер, ең жақсы, ең нашар және орташа жағдайды талдау, уақыт-кеңістік арақатынасы (time–space tradeoffs) және жоғарғы және төменгі шектер. Кіші массивтерді оңтайлы (ең аз салыстырулар мен алмастырулар арқылы) немесе жылдам (машинаның ерекшеліктерін ескере отырып) сұрыптау мәселесі әлі де зерттеу нысаны болып табылады, және оның шешімі тек өте кіші массивтер үшін ғана (<20 элемент) белгілі. Сол сияқты, параллель машинада сұрыптаудың (әртүрлі анықтамалар бойынша) оңтайлы болуы да ашық зерттеу тақырыбы болып табылады.

Тұрақтылық

Тұрақты сұрыптау алгоритмдері бірдей элементтерді кірісте пайда болған ретпен сұрыптайды. Мысалы, оң жақтағы карталарды сұрыптау мысалында карталар олардың ранкі бойынша сұрыпталады, ал олардың костюмі ескерілмейді. Бұл бастапқы тізімнің дұрыс сұрыпталған бірнеше нұсқасын жасауға мүмкіндік береді. Тұрақты сұрыптау алгоритмдері мына ережеге сәйкес осылардың біреуін таңдайды: егер екі элемент тең болып салыстырылса (екі 5 карта сияқты), онда олардың салыстырмалы тәртібі сақталады, яғни егер бірін екіншісінен бұрын енгізсе, ол шығыста екіншісінен бұрын келеді. Тұрақтылық – бір дерек жиынтығында бірнеше сұрыптаудың реттілігін сақтау үшін маңызды. Мысалы, оқушылардың аты мен сынып бөлімінен тұратын жазбалары динамикалық түрде, алдымен аты бойынша, содан кейін сынып бөлімі бойынша сұрыпталады делік. Егер екі жағдайда да тұрақты сұрыптау алгоритмі қолданылса, сынып бойынша сұрыптау секциясы аты-жөні ретін өзгертпейді; тұрақсыз сұрыптаумен, бөлім бойынша сұрыптау аты-жөні ретін араластырып, студенттердің әліпбилік емес тізіміне әкелуі мүмкін. Формальды түрде, сұрыпталатын деректер дерек немесе мәндердің туплісі ретінде ұсынылуы мүмкін, ал сұрыптау үшін пайдаланылатын деректердің бөлігі кілт деп аталады. Карталар мысалында карталар жазба ретінде (ранк, костюм) ұсынылады, ал кілт – бұл ранкі. Сұрыптау алгоритмі тұрақты болып есептеледі, егер бір кілті бар R және S екі жазбасы болған кезде, және R бастапқы тізімде S алдында пайда болса, онда R әрқашан сұрыпталған тізімде S алдында пайда болады. Тең элементтер ажыратылмайтын болса, мысалы бүтін сандар немесе жалпы алғанда, барлық элемент кілт болып табылатын кез келген деректер үшін тұрақтылық мәселе емес. Тұрақтылық барлық кілттер әр түрлі болса да мәселе емес. Тұрақсыз сұрыптау алгоритмдерін тұрақты болу үшін арнайы іске асыруға болады. Мұны істеудің бір жолы – кілтті салыстыруды жасанды түрде кеңейту, сондықтан екі нысанның тең кілттері арасындағы салыстырулар түпнұсқалық кіріс тізіміндегі жазбалардың реттілігін пайдаланып, теңдікті бұзушы ретінде шешіледі. Алайда, бұл реттілікті есте сақтау үшін қосымша уақыт пен орын қажет болуы мүмкін. Тұрақты сұрыптау алгоритмдерінің бір қолданысы – негізгі және қосымша кілттерді пайдалана отырып тізімді сұрыптау. Мысалы, біз карталарды сұрыптағымыз келсін, онда костюмдер ретімен клубтар (♣), ромбтар (♦), жүректер (♥), пикалар (♠) және әр костюмнің ішінде карталар ранкі бойынша сұрыпталады. Бұл алдымен карталарды ранкі бойынша сұрыптау (кез келген сұрыптауды қолдану арқылы) арқылы, содан кейін костюм бойынша тұрақты сұрыптау арқылы орындалуы мүмкін: Әрбір костюмнің ішінде тұрақты сұрыптау бұрыннан жасалған ранкі бойынша реттілікті сақтайды. Бұл идеяны кез келген кілттер санына қолдануға болады және радикс сұрыптау арқылы пайдаланылады. Осыған ұқсас әсерді тұрақсыз сұрыптаумен лексикографиялық кілтті салыстыру арқылы қол жеткізуге болады, мысалы, алдымен костюм бойынша салыстырады, содан кейін костюмдер бірдей болса, ранкі бойынша салыстырады.

Stable sort algorithms sort equal elements in the same order that they appear in the input. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. This allows the possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal (like the two 5 cards), then their relative order will be preserved, i. e. if one comes before the other in the input, it will come before the other in the output. Stability is important to preserve order over multiple sorts on the same data set. For example, say that student records consisting of name and class section are sorted dynamically, first by name, then by class section. If a stable sorting algorithm is used in both cases, the sort by class section operation will not change the name order; with an unstable sort, it could be that sorting by section shuffles the name order, resulting in a nonalphabetical list of students. More formally, the data being sorted can be represented as a record or tuple of values, and the part of the data that is used for sorting is called the key. In the card example, cards are represented as a record (rank, suit), and the key is the rank. A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list. When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue. Stability is also not an issue if all keys are different. Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original input list as a tie breaker. Remembering this order, however, may require additional time and space. One application for stable sorting algorithms is sorting a list using a primary and secondary key. For example, suppose we wish to sort a hand of cards such that the suits are in the order clubs (♣), diamonds (♦), hearts (♥), spades (♠), and within each suit, the cards are sorted by rank. This can be done by first sorting the cards by rank (using any sort), and then doing a stable sort by suit:

Within each suit, the stable sort preserves the ordering by rank that was already done. This idea can be extended to any number of keys and is utilised by radix sort. The same effect can be achieved with an unstable sort by using a lexicographic key comparison, which, e. g., compares first by suit, and then compares by rank if the suits are the same.

Алгоритмдерді салыстыру

Бұл кестелерде n – сұрыпталуға тиіс жазбалар саны. "Ең жақсы", "Орташа" және "Ең нашар" бағандары әр жағдайдағы уақыт күрделілігін көрсетеді, барлық кілттердің ұзындығы тұрақты деп есептесек, барлық салыстырулар, алмастырулар және басқа операциялар тұрақты уақытта орындалуы мүмкін. "Жад" – тізімнің өзі пайдаланатын жадтан өзге, қосымша қажетті сақтау көлемі, осы болжам бойынша. Көрсетілген орындалу уақыты мен жад талаптары үлкен O нотациясымен берілген, сондықтан логарифмдердің негізі маңызды емес. log^(2) n белгісі (log n)^(2) дегенді білдіреді.

Салыстыру түрлері

Төменде салыстыру сұрыптауларының кестесі берілген. Салыстыру сұрыптаулары орташа жағдайда O(n log n)-нен жақсы нәтиже бере алмайды. + Салыстыру сұрыптаулары Атауы Ең жақсы Орташа Ең нашар Жады Тұрақты Әдіс Басқа ескертулер Орнында біріктіру сұрыптау — — Иә Біріктіру Тұрақты жерде біріктіруге негізделген тұрақты сұрыптау ретінде жүзеге асырылуы мүмкін. Heapsort Жоқ Таңдау Introsort Жоқ Бөлу және таңдау STL-дің бірнеше нұсқаларында қолданылады. Біріктіру сұрыптау Иә Біріктіру Үш венгр алгоритмін қолдана отырып, жоғары параллельдеуге болады (O(log n) дейін). Турнирлік сұрыптау Жоқ Таңдау Heapsort-тың өзгеруі. Ағаш сұрыптау Иә Кірістіру Өзін-өзі теңгерілген бинарлық іздеу ағашын пайдаланғанда. Блок сұрыптау Иә Кірістіру және біріктіру Блоктық негіздегі O(n) орнында біріктіру алгоритмін төменнен жоғарыға қарай біріктіру сұрыптаумен біріктіреді. Smoothsort Жоқ Таңдау Дәстүрлі екілік үйіндіге емес, Леонардо тізбегіне негізделген үйіндінің бейімделген түрі. Timsort Иә Кірістіру және біріктіру Деректер сұрыпталған немесе кері сұрыпталған болса, n-1 салыстыру жасайды. Шыдамдылық сұрыптау Жоқ Кірістіру және таңдау O(n log n) уақытында ең ұзын өсуші кіші тізбектердің барлығын табады. Cubesort Иә Кірістіру Деректер бұрыннан сұрыпталған немесе кері сұрыпталған болса, n-1 салыстыру жасайды. Жылдам сұрыптау Жоқ Бөлу Жылдам сұрыптау әдетте O(log n) қапшық кеңістігімен орнында жасалады. Кітапхана сұрыптау Жоқ Кірістіру Салымды сұрыптауға ұқсас. Оның жоғары ықтималдықпен уақыт шектеріне сәйкес келуі үшін кірістіруді кездейсоқ түрде өзгерту қажет, бұл оны тұрақсыз етеді. Shellsort Жоқ Кірістіру Шағын код көлемі. Comb sort Жоқ Алмасу Орташа есеппен көпіршік сұрыптаудан жылдам. Салым сұрыптау Иә Кірістіру O(n + d), ең нашар жағдайда d инверсиясы бар тізбектер үшін. Көпіршік сұрыптау Иә Алмасу Шағын код көлемі. Коктейль шайқағыш сұрыптау Иә Алмасу Тізімнің соңындағы кішкентай мәндермен жақсы жұмыс жасайтын көпіршік сұрыптаудың түрі. Gnome sort Иә Алмасу Шағын код көлемі. Жұп-тақ сұрыптау Иә Алмасу Параллель процессорларда оңай орындалуы мүмкін. Қарапайым құймақ сұрыптау Жоқ Таңдау Әрбір таңдау сканнан кейін екі элементті алмастырудың орнына кері бұруды қолданатын таңдау сұрыптаудың түрі. Strand sort Иә Таңдау Таңдау сұрыптау. Exchange sort Жоқ Алмасу Шағын код көлемі. Cycle sort Жоқ Таңдау Теориялық түрде жазулардың ең оңтайлы санымен орнында жасалады.

Below is a table of comparison sorts. A comparison sort cannot perform better than O(n log n) on average. + Comparison sorts Name Best Average Worst Memory Stable Method Other notes In place merge sort — — Yes Merging Can be implemented as a stable sort based on stable in place merging. Heapsort No Selection Introsort No Partitioning & Selection Used in several STL implementations. Merge sort Yes Merging Highly parallelizable (up to O(log n) using the Three Hungarians' Algorithm). Tournament sort No Selection Variation of Heapsort. Tree sort Yes Insertion When using a self balancing binary search tree. Block sort Yes Insertion & Merging Combine a block based O(n) in place merge algorithm with a bottom up merge sort. Smoothsort No Selection An adaptive variant of heapsort based upon the Leonardo sequence rather than a traditional binary heap. Timsort Yes Insertion & Merging Makes n 1 comparisons when the data is already sorted or reverse sorted. Patience sorting No Insertion & Selection Finds all the longest increasing subsequences in O(n log n). Cubesort Yes Insertion Makes n 1 comparisons when the data is already sorted or reverse sorted. Quicksort No Partitioning Quicksort is usually done in place with O(log n) stack space. Library sort No InsertionSimilar to a gapped insertion sort. It requires randomly permuting the input to warrant with high probability time bounds, which makes it not stable. Shellsort No Insertion Small code size. Comb sort No Exchanging Faster than bubble sort on average. Insertion sort Yes Insertion O(n + d), in the worst case over sequences that have d inversions. Bubble sort Yes Exchanging Tiny code size. Cocktail shaker sort Yes ExchangingA variant of Bubblesort which deals well with small values at end of list Gnome sort Yes Exchanging Tiny code size. Odd–even sort Yes Exchanging Can be run on parallel processors easily. Simple pancake sort No Selection A variant of selection sort that uses reversals, instead of just swapping the two items, after each selection scan. Strand sort Yes Selection Selection sort No Selection Stable with O(n) extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items. Exchange sort No Exchanging Tiny code size. Cycle sort No Selection In place with theoretically optimal number of writes.

Танымал сұрыптау алгоритмдері

Сорттау алгоритмдерінің саны көп болғанымен, практикалық қолдануда бірнеше алгоритмдер басым. Кірістіру сұрыптау (insertion sort) кішкентай деректер жиынтықтары үшін кеңінен қолданылады, ал үлкен деректер жиынтықтары үшін асимптотикалық тиімді сұрыптау қолданылады, көбінесе үймелі сұрыптау (heapsort), біріктіру сұрыптау (merge sort) немесе жылдам сұрыптау (quicksort). Тиімді жүзеге асырулар әдетте гибридті алгоритмді пайдаланады, рекурсияның төменгі деңгейіндегі кіші тізімдерді кірістіру сұрыптаумен біріктіре отырып, жалпы сұрыптау үшін асимптотикалық тиімді алгоритмді қолданады. Жоғары сапалы жүзеге асырулар күрделірек нұсқаларды қолданады, мысалы, Timsort (біріктіру сұрыптау, кірістіру сұрыптау және қосымша логика), Android, Java және Python-да қолданылады, және introsort (жылдам сұрыптау және үймелі сұрыптау), кейбір C++ сұрыптау жүзеге асыруларында және .NET-те (өзгертілген түрлерінде) қолданылады. Нақты белгілі бір интервалдағы сандар сияқты шектеулі деректер үшін, санау сұрыптау (counting sort) немесе радикс сұрыптау (radix sort) сияқты тарату сұрыптары кеңінен қолданылады. Көпіршік сұрыптау (bubble sort) және оның нұсқалары практикада сирек қолданылады, бірақ оқыту және теориялық талқылауларда жиі кездеседі. Физикалық түрде объектілерді сұрыптағанда (мысалы, қағаздарды, емтихан парақтарын немесе кітаптарды әліпбилік тәртіппен реттегенде), адамдар көбінесе кішкентай жиынтықтар үшін кірістіру сұрыптауды интуитивті түрде қолданады. Үлкен жиынтықтар үшін адамдар көбінесе алдымен топқа бөледі, мысалы, бастапқы әріп бойынша, және бірнеше топқа бөлу өте үлкен жиынтықтарды практикалық түрде сұрыптауға мүмкіндік береді. Көбінесе кеңістік салыстырмалы түрде арзан, мысалы, еденге немесе үлкен аумаққа объектілерді тарату арқылы, бірақ операциялар қымбат, әсіресе объектіні үлкен қашықтыққа жылжыту – деректерге жылдам қол жеткізу маңызды. Біріктіру сұрыптау физикалық объектілер үшін де практикалық, әсіресе екі қолды пайдалануға болады, әр тізімді біріктіру үшін бір қолдан, ал үймелі сұрыптау (heapsort) немесе жылдам сұрыптау (quicksort) сияқты басқа алгоритмдер адамдарға қолайсыз. Кітапхана сұрыптау (library sort) сияқты, бос орындарды қалдыратын кірістіру сұрыптаудың (insertion sort) нұсқасы да физикалық қолдану үшін тиімді.

Қарапайым түрлері

Ең қарапайым екі түрі – енгізу сұрыптау және таңдау сұрыптау. Екеуі де аз көлемді деректерде тиімді, себебі төмен шығындарға ие, бірақ үлкен деректерде тиімді емес. Енгізу сұрыптау, практикада таңдау сұрыптаудан көбінесе жылдам болады, себебі салыстырулардың саны аз және дерлік реттелген деректерде жақсы жұмыс істейді, осылайша, практикада оған басымдық беріледі. Бірақ таңдау сұрыптау жазу операцияларын азайтады, сондықтан жазу жылдамдығы шектеулі болған жағдайда қолданылады.

Салым түрлендіруі

Салым сұрыптау – кішкентай тізімдер мен көбінесе реттелген тізімдер үшін салыстырмалы түрде тиімді, қарапайым сұрыптау алгоритмі. Ол көбінесе күрделірек алгоритмдердің бір бөлігі ретінде қолданылады. Алгоритм тізімнен элементтерді біріншісінен бастап алып, оларды жаңа реттелген тізімге дұрыс орнына қою арқылы жұмыс істейді – бұл ақшаны әмиянына салып қоюға ұқсас. Массивтерде жаңа тізім мен қалған элементтер массивтің жадын бірге пайдалана алады, бірақ қою операциясы қымбатқа түседі, себебі барлық келесі элементтерді бір қадамға жылдыру қажет. Шелсорт – үлкен тізімдер үшін тиімдірек салым сұрыптаудың түрі.

Таңдау сұрыптау

Таңдау сұрыптау - орнында салыстыру арқылы ішкі сұрыптау алгоритмі. Оның күрделілігі O(n²), бұл оны үлкен тізімдерде тиімсіз етеді және көбінесе ұқсас енгізу сұрыптауынан нашар жұмыс істейді. Таңдау сұрыптау қарапайымдылығымен ерекшеленеді, сонымен қатар кейбір жағдайларда күрделі алгоритмдерге қарағанда артықшылықтары бар. Алгоритм ең кішкентай мәнді тауып, оны тізімнің бірінші орнымен ауыстырады, содан кейін тізімнің қалған бөлігі үшін осы қадамдарды қайталайды. Ол n-нен аспайтын ауыстыру операцияларын жасайды, сондықтан ауыстыру өте қымбат болған жағдайларда пайдалы.

Тиімді сорттар

Практикалық жалпы сұрыптау алгоритмдері көбінесе орташа уақыт күрделілігі (және әдетте ең нашар жағдайда күрделілігі) O(n log n) болатын алгоритмға негізделген, олардың ең көп тарағандары – үймелі сұрыптау, біріктіру сұрыптау және жылдам сұрыптау. Әрқайсысының артықшылықтары мен кемшіліктері бар, ең маңыздысы – біріктіру сұрыптаудың қарапайым іске асырылуы O(n) қосымша жадты пайдаланады, ал жылдам сұрыптаудың қарапайым іске асырылуы O(n²) ең нашар жағдайда күрделілікке ие. Бұл мәселелерді күрделі алгоритмнің есебінен шешуге немесе жақсартуға болады. Бұл алгоритмдер кездейсоқ деректерде асимптотикалық тиімді болғанымен, нақты деректердегі практикалық тиімділік үшін түрлі өзгертулер қолданылады. Біріншіден, бұл алгоритмдердің қосымша шығындары кішкентай деректерде маңызды болатындықтан, көбінесе гибридтік алгоритм қолданылады, әдетте деректер жеткілікті кішкентай болғанда енгізу сұрыптауына ауысады. Екіншіден, алгоритмдер жиі реттелген немесе дерлік реттелген деректерде нашар жұмыс істейді – бұл нақты деректерде жиі кездеседі және тиісті алгоритмдер арқылы O(n) уақытында сұрыпталуы мүмкін. Соңында, олар тұрақсыз болуы мүмкін, ал тұрақтылық көбінесе қажетті қасиет болып табылады. Сондықтан, Timsort (біріктіру сұрыптауына негізделген) немесе introsort (жылдам сұрыптауға негізделген, үймелі сұрыптауға қайта оралады) сияқты күрделі алгоритмдер жиі қолданылады.

Біріктіру сұрыптау

Merge sort – жаңа сұрыпталған тізімге бұрыннан сұрыпталған тізімдерді біріктірудің қарапайымдығын пайдаланады. Ол әр екі элементті салыстырудан бастайды (мысалы, 1-ді 2-мен, содан кейін 3-ты 4-пен) және егер бірінші элемент екіншісінен кейін келуі керек болса, оларды ауыстырады. Содан кейін ол екі элементтен тұратын әрбір тізімді төрт элементтен тұратын тізімдерге біріктіреді, содан кейін осы төрт элементтен тұратын тізімдерді біріктіреді, және т.б.; соңында екі тізім біріктіріліп, соңғы сұрыпталған тізім құрылады. Мұнда сипатталған алгоритмдердің ішінде бұл өте үлкен тізімдерге жақсы масштабталатын алғашқы алгоритм, өйткені оның ең нашар жағдайдағы жұмыс уақыты O(n log n) болып табылады. Ол массивтер ғана емес, тізімдерге де оңай қолданылады, себебі ол тек тізбектей қол жеткізуді қажет етеді, кездейсоқ емес. Дегенмен, ол қосымша O(n) кеңістік күрделілігіне ие және қарапайым іске асыруларда көп көшірулерді қамтиды. Біріктіру сұрыптау әдісі жақында практикалық іске асыруларда танымалдылығының артуына куә болды, себебі ол күрделі алгоритм Timsort-та қолданылады, ол Python және Java бағдарламалау тілдеріндегі стандартты сұрыптау процедурасы ретінде қолданылады (JDK7 нұсқасы бойынша). Merge sort өзі Perl-де стандартты процедура болып табылады, және кем дегенде 2000 жылдан бері JDK1.3 нұсқасында Java-да қолданылып келеді.

Топ түрін

Heapsort – таңдау сұрыптаудың әлдеқайда тиімді түрі. Ол да тізімнің ең үлкен (немесе ең кіші) элементін анықтап, оны тізімнің соңына (немесе басына) қойып, содан кейін тізімнің қалған бөлігімен жұмысты жалғастырады, бірақ бұл міндетті "үйінді" деп аталатын дерек құрылымын, екілік ағаштың ерекше түрін пайдалану арқылы тиімді орындайды. Деректер тізімі үйіндіге айналғаннан кейін, түбір түйіні ең үлкен (немесе ең кіші) элемент екені кепілдігі беріледі. Ол алынып, тізімнің соңына қойылғанда, үйінді қайта құрылады, сонда қалған ең үлкен элемент түбірге көшеді. Үйіндіні пайдалану арқасында келесі үлкен элементті табу O(log n) уақыт алады, ал қарапайым таңдау сұрыптамасындағы сызықтық іздеу үшін O(n) уақыт керек. Бұл Heapsort-қа O(n log n) уақытында жұмыс істеуге мүмкіндік береді, және бұл ең нашар жағдайдағы күрделілік те болып табылады.

Тез сұрыптау

Quicksort – бөл және басқар алгоритмі, ол бөлу операциясына негізделген: массивті бөлу үшін півот деп аталатын элемент таңдалады. Півоттан кішi элементтердiң барлығы одан бұрын жылжытылады, ал үлкен элементтер одан кейiн жылжытылады. Бұл сызықтық уақытта және орнында тиімді түрде жасалуы мүмкін. Содан кейін кішi және үлкен қосалқы тізімдер рекурсивті түрде сұрыпталады. Бұл O(n log n) орташа уақыт күрделілігін береді, төмен шығындармен, сондықтан бұл танымал алгоритм. Quicksort-тың тиімді нұсқалары (орнында бөлумен) әдетте тұрақсыз және біршама күрделі болып табылады, бірақ практикада ең жылдам сұрыптау алгоритмдерінің бірі болып табылады. Шамалы O(log n) кеңістік қолданысымен қатар, quicksort – ең танымал сұрыптау алгоритмдерінің бірі және көптеген стандартты бағдарламалау кітапханаларында қолжетімді. Quicksort туралы маңызды ескерту – ең жаман жағдайдағы орындалуы O(n^2) екендігі; бұл сирек болса да, қарапайым нұсқаларда (бірінші немесе соңғы элементті півот ретінде таңдау) сұрыпталған деректер үшін орын алады, бұл жиі кездесетін жағдай. Quicksort-тағы ең күрделі мәселе – жақсы півот элементін таңдау, өйткені півоттардың нашар таңдалуы O(n^2) өнімділігін күрт баяулатуы мүмкін, ал півоттардың жақсы таңдалуы O(n log n) өнімділігін береді, бұл асимптотикалық жағынан оптималды. Мысалы, әр қадамда медиана півот ретінде таңдалса, алгоритм O(n log n) уақытында жұмыс істейді. Медиананы табу, мысалы, медиананың медианасын таңдау алгоритмі арқылы, сұрыпталмаған тізімдерде O(n) операциясы болып табылады, сондықтан сұрыптаумен байланысты айтарлықтай шығындар тудырады. Іс жүзінде кездейсоқ півотты таңдау көбінесе O(n log n) өнімділігін қамтамасыз етеді. Егер O(n log n) өнімділігіне кепілдік беру маңызды болса, оған жету үшін қарапайым өзгеріс бар. Musser ұсынған идея – рекурсияның максималды тереңдігіне шектеу қою. Егер бұл шек асып кетсе, сұрыптау heapsort алгоритмін пайдаланып жалғастырылады. Musser бұл шек кездейсоқ реттелген массивте орташа күтілетін максималды рекурсия тереңдігінен шамамен екі есе үлкен болуы керек деп ұсынды.

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array, an element called a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and in place. The lesser and greater sublists are then recursively sorted. This yields average time complexity of O(n log n), with low overhead, and thus this is a popular algorithm. Efficient implementations of quicksort (with in place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries. The important caveat about quicksort is that its worst case performance is O(n2); while this is rare, in naive implementations (choosing the first or last element as pivot) this occurs for sorted data, which is a common case. The most complex issue in quicksort is thus choosing a good pivot element, as consistently poor choices of pivots can result in drastically slower O(n2) performance, but good choice of pivots yields O(n log n) performance, which is asymptotically optimal. For example, if at each step the median is chosen as the pivot then the algorithm works in O(n log n). Finding the median, such as by the median of medians selection algorithm is however an O(n) operation on unsorted lists and therefore exacts significant overhead with sorting. In practice choosing a random pivot almost certainly yields O(n log n) performance. If a guarantee of O(n log n) performance is important, there is a simple modification to achieve that. The idea, due to Musser, is to set a limit on the maximum depth of recursion. If that limit is exceeded, then sorting is continued using the heapsort algorithm. Musser proposed that the limit should be , which is approximately twice the maximum recursion depth one would expect on average with a randomly ordered array.

Қалқалар сұрыптау

Шелсортты 1959 жылы Дональд Шелл ойлап тапты. Ол бірден бірнеше элементті орнынан жылжыту арқылы енгізу сұрыптауын жақсартады. Шелсорттың негізгі идеясы – енгізу сұрыптау O(kn) уақытында орындалады, мұнда k – орны ауысқан екі элемент арасындағы ең үлкен қашықтық. Яғни, әдетте ол O(n²) уақытында жұмыс істейді, бірақ деректер көбінесе реттелген болса, тек бірнеше элемент орнынан шығып кетсе, тезірек орындайды. Сондықтан, алдымен алыстағы элементтерді сұрыптап, содан кейін сұрыпталатын элементтер арасындағы аралықты біртіндеп қысқарту арқылы, соңғы сұрыптау өте жылдам орындалады. Бір әдісі – деректер тізбегін екі өлшемді массивке орналастырып, содан кейін массивтің бағандарын енгізу сұрыптау арқылы сұрыптау. Шелсорттың ең нашар жағдайдағы уақыт күрделілігі әлі шешілмеген мәселе және қолданылған аралық тізбегіне байланысты, белгілі күрделілігі O(n²) мен O(n4/3) және Θ(n log₂ n) арасында. Бұл, Шелсорттың орнында орындалуымен, салыстырмалы түрде аз кодты қажет етуімен және қоңырау стегін пайдалануды қажет етпеуімен біріктіріледі, оны жадтың шектеулі болған жағдайларда, мысалы, кіріктірілген жүйелерде және операциялық жүйе ядроларында пайдалануға ыңғайлы етеді.

Шашырауыш сұрыптау және нұсқалары

Bubble sort, сондай-ақ Comb sort және cocktail sort сияқты түрлері, қарапайым, бірақ өте тиімсіз сұрыптау алгоритмдері болып табылады. Олар талдаудың қарапайымдылығы себепті бастауыш оқулықтарда жиі кездеседі, алайда практикада олар сирек қолданылады.

Бұзық түрлендіру

Bubble sort – қарапайым сұрыптау алгоритмі. Алгоритм деректер жиынтығының басында басталады. Ол алғашқы екі элементті салыстырады, егер біріншісі екіншісінен үлкен болса, оларды алмастырады. Ол осыны әрбір жапсырған элементтер жұбы үшін деректер жиынтығының соңына дейін жалғастырады. Содан кейін ол алғашқы екі элементтен қайта басталады, соңғы өтуде алмасулар болмағанға дейін қайталайды. Бұл алгоритмнің орташа және ең нашар жағдайдағы уақыттық тиімділігі O(n²), сондықтан ол үлкен, ретсіз деректер жиынтығын сұрыптау үшін сирек қолданылады. Bubble sort кішкентай мөлшердегі элементтерді сұрыптау үшін қолданылуы мүмкін (оның асимптотикалық тиімсіздігі үлкен кемшілік емес). Bubble sort кез келген ұзындықтағы, көбінесе реттелген тізімдерде тиімді қолданылуы мүмкін (яғни элементтер орнынан көп алшақтамаған). Мысалы, егер элементтердің кез келген саны бір ғана орынмен қате орналасқан болса (мысалы, 0123546789 және 1032547698), Bubble sort алмасу арқылы оларды бірінші өтуде ретке келтіреді, екінші өтуде барлық элементтер ретпен екенін анықтайды, сондықтан сұрыптауға тек 2n уақыт кетеді.

Таңбалау

Comb sort – бұл көпіршік сұрыптауына негізделген, салыстырмалы түрде қарапайым сұрыптау алгоритмі, оны 1980 жылы Влодзимеж Добошевич әзірлеген. Кейіннен Стивен Лейси мен Ричард Бокс оны қайта ашып, 1991 жылғы сәуір айындағы Byte Magazine журналындағы мақаласы арқылы танымал етті. Негізгі идея – тізімнің соңына жақын орналасқан кіші мәндерді, яғни «бақаларды» жою, себебі көпіршік сұрыптауында олар сұрыптау процесін айтарлықтай баяулатады. (Тізімнің басындағы үлкен мәндер, яғни «қояндар», көпіршік сұрыптауында мәселе тудырмайды.) Алгоритм бастапқыда массивтегі бір-бірінен белгілі бір қашықтықта тұрған элементтерді алмастыру арқылы мұны іске асырады, тек қана жанындағы элементтерді алмастыру емес, содан кейін таңдалған қашықтықты азайтады, осылайша ол қалыпты көпіршік сұрыптауы сияқты жұмыс істей бастайды. Осылайша, егер Shellsort-ты бір-бірінен белгілі бір қашықтықта орналасқан элементтерді алмастыратын енгізу сұрыптауының жалпыланған түрі деп қарастырсақ, comb sort-ты көпіршік сұрыптауына қолданылатын сол жалпылау ретінде қарастыруға болады.

Ауыстыруды сұрыптау

Алмасу сұрыптауды кейде көпіршік сұрыптаумен шатастырады, бірақ алгоритмдер шын мәнінде ерекшеленеді. Алмасу сұрыптау бірінші элементті оның жоғарысындағы барлық элементтермен салыстыру арқылы жұмыс істейді, қажет болған жағдайда оларды ауыстырады, осылайша бірінші элементтің соңғы сұрыпталу ретіне сәйкес келетініне кепілдік береді; содан кейін екінші элемент үшін де осылай істейді, және т.б. Бұл сұрыптау үшін бір рет өту кезінде тізімнің бұрыннан сұрыпталған екенін анықтау артықшылығы көпіршік сұрыптауда бар, бірақ ең нашар жағдайда алмасу сұрыптау тұрақты фактормен (сұрыпталуға тиіс деректерді бір рет өтуден кем; жалғыз салыстырулардың жартысы) көпіршік сұрыптаудан жылдам болуы мүмкін. Кез келген қарапайым O(n²) сұрыптау сияқты, ол өте кішкентай деректер жиынында жеткілікті жылдам болуы мүмкін, бірақ жалпы алғанда енгізу сұрыптау жылдам болады.

Тарату түрлері

Тарату арқылы сұрыптау – деректер кірістік деректерден бірнеше аралық құрылымдарға таратылып, кейін жиналып, нәтижеге шығарылатын кез келген сұрыптау алгоритмі. Мысалы, шелек сұрыптау және флэш-сұрыптау – таратуға негізделген сұрыптау алгоритмдерінің екеуі. Тарату арқылы сұрыптау алгоритмдерін бір процессорда қолдануға болады, немесе олар үлестірілген алгоритм болып табылуы мүмкін, онда жеке кіші жиынтықтар әртүрлі процессорларда бөлек сұрыпталып, содан кейін біріктіріледі. Бұл бір компьютердің жадына сыймайтын деректерді сыртқы түрде сұрыптауға мүмкіндік береді.

Санау түрі

Санау сұрыптау әрбір кіріс мәнінің белгілі бір мүмкіндіктер жиынына, S-ке тиесілі екені белгілі болғанда қолданылады. Алгоритм O(|S| + n) уақытта және O(|S|) жадта жұмыс істейді, мұнда n – кіріс тізімінің ұзындығы. Ол |S| өлшемді бүтін сандар массивін құру арқылы жұмыс істейді және кірістегі S жиынының i-мүшесінің қайсысын қанша рет кездесетінін санау үшін i-інші бөлімшені пайдаланады. Содан кейін әрбір кіріс оның сәйкес бөлімшесінің мәнін арттыру арқылы есептеледі. Кейін санау массиві кіріс мәндерін ретпен орналастыру үшін итерацияланады. Бұл сұрыптау алгоритмі жиі қолданылмайды, себебі алгоритм тиімді болуы үшін S жеткілікті кішкентай болуы керек, бірақ ол өте жылдам және n өскен сайын үлкен асимптотикалық көрсеткіштерді көрсетеді. Сондай-ақ, тұрақты мінез-құлықты қамтамасыз ету үшін оны өзгертуге болады.

Қапшықты сұрыптау

Bucket sort – массивті шекті сандағы бөліктерге бөліп, санау сұрыптауын жалпылайтын, бөл және басқар (divide and conquer) алгоритмі. Әрбір бөлік жеке-жеке басқа сұрыптау алгоритмін қолдану арқылы немесе bucket sort алгоритмін рекурсивті түрде қолдану арқылы сұрыпталады. Bucket sort деректер жиынтығының элементтері барлық бөліктерге тең бөлінген кезде ең жақсы жұмыс істейді.

Түбірлік сұрыптау

Радикс сұрыптау – сандарды жеке цифрларын өңдеу арқылы сұрыптайтын алгоритм. Әрқайсысы k цифрдан тұратын n сан O(n · k) уақытында сұрыпталады. Радикс сұрыптау әр санның цифрларын ең кіші мәнді цифрдан (LSD) немесе ең маңызды цифрдан (MSD) бастап өңдей алады. LSD алгоритмі тізімді бірінші кезекте ең кіші мәнді цифр бойынша сұрыптайды, сонымен бірге салыстырмалы ретін сақтап, тұрақты сұрыптауды қолданады. Содан кейін оларды келесі цифр бойынша сұрыптайды, және т.с.с., ең кіші мәндіден ең маңыздысына дейін, нәтижесінде сұрыпталған тізім шығады. LSD радикс сұрыптауы тұрақты сұрыптауды қажет етеді, ал MSD радикс сұрыптау алгоритміне ол қажет емес (егер тұрақты сұрыптау қажет болмаса). Орнындағы MSD радикс сұрыптау тұрақты емес. Радикс сұрыптау ішкі жұмысында санау сұрыптау алгоритмін пайдалану жиі кездеседі. Кіші топтар үшін енгізу сұрыптауын қолдану сияқты гибридтік сұрыптау тәсілі радикс сұрыптаудың тиімділігін едәуір арттырады.

Жад пайдалану үлгілері және индексті сұрыптау

Сортталатын массивтің мөлшері қол жетімді негізгі жадыға жақындағанда немесе одан асып кеткенде, сондықтан (әлдеқайда баяу) дискі немесе ауыстыру жады қолданылуы керек болғандықтан, сұрыптау алгоритмінің жадты пайдалану схемасы маңызды болады. Массив RAM-ге оңай сыйып, тиімді болған алгоритм, бұл жағдайда тиімсіз болуы мүмкін. Мұндай жағдайда, салыстырулардың жалпы саны (салыстырмалы түрде) маңыздылығы төмендейді, ал жад бөлімдерін дискіге көшіру немесе ауыстыру қажеттілігі алгоритмнің өнімділік ерекшеліктеріне үстемдік ете алады. Сондықтан, өтулер саны және салыстырулардың орналасуы, салыстырулардың өзінен маңыздырақ болуы мүмкін, себебі жақын орналасқан элементтердің бір-бірімен салыстырылуы жүйелік шина жылдамдығымен (немесе кэшпен, тіпті процессор жылдамдығымен) жүзеге асады, бұл дискінің жылдамдығымен салыстырғанда дерлік жедел болады. Мысалы, кең таралған рекурсивті жылдам сұрыптау алгоритмі жеткілікті RAM болғанда жақсы өнімділік көрсетеді, бірақ массив RAM-ге сыймағанда, массив бөліктерін көшірудің рекурсивті әдісіне байланысты тиімділігі төмендейді, себебі дискіге көптеген баяу көшіру немесе жылжыту операцияларын тудыруы мүмкін. Мұндай жағдайда, тіпті жалпы салыстыру саны көп болса да, басқа алгоритм тиімдірек болуы мүмкін. Бұл мәселені шешудің бір жолы, күрделі жазбаларды (мысалы, реляциялық деректер базасында) салыстырмалы түрде кішкентай кілттік өріс бойынша сұрыптағанда жақсы жұмыс істейді: массивке индекс құрып, содан кейін массивтің өзін емес, осы индексті сұрыптау. (Массивтің сұрыпталған нұсқасын индекс бойынша бір рет оқып өту арқылы жасауға болады, бірақ көбінесе тіпті бұл қажет емес, өйткені сұрыпталған индекс жеткілікті.) Индекс массивтің өзінен әлдеқайда кішкентай болғандықтан, массив сыймайтын жадта оңай орналаса алады, бұл дискіге ауыстыру мәселесін тиімді түрде жояды. Бұл процедура кейде "белгі сұрыптау" деп аталады. Жад көлемі мәселесін шешудің тағы бір тәсілі – сыртқы сұрыптауды қолдану, мысалы, екі алгоритмді біріктіру арқылы, олардың әрқайсысының күшін пайдаланып, жалпы өнімділікті жақсарту. Мысалы, массив RAM-ге сыятын мөлшердегі бөліктерге бөлінуі мүмкін, әр бөліктің мазмұны тиімді алгоритм (мысалы, жылдам сұрыптау) арқылы сұрыпталады, ал нәтижелер біріктіру сұрыптауында қолданылатын сияқты k-жолды біріктіру арқылы біріктіріледі. Бұл, тізім бойынша біріктіру немесе жылдам сұрыптауды орындаудан жылдам. Тәсілдерді де біріктіруге болады. Өте үлкен деректер жиынтығын сұрыптау үшін, жүйелік жадтан әлдеқайда асып түсетін жағдайда, тіпті индексті де виртуалды жадпен ақылға қонымды жұмыс істеуге арналған алгоритм немесе алгоритмдер комбинациясын қолдану арқылы сұрыптау қажет болуы мүмкін, яғни ауыстыру мөлшерін азайту үшін.

When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in RAM may become impractical. In this scenario, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at system bus speed (or, with caching, even at CPU speed), which, compared to disk speed, is virtually instantaneous. For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario, another algorithm may be preferable even if it requires more total comparisons. One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk swapping problem. This procedure is sometimes called "tag sort". Another technique for overcoming the memory size problem is using external sorting, for example one of the ways is to combine two algorithms in a way that takes advantage of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit in RAM, the contents of each chunk sorted using an efficient algorithm (such as quicksort), and the results merged using a k way merge similar to that used in merge sort. This is faster than performing either merge sort or quicksort over the entire list. Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual memory, i. e., to reduce the amount of swapping required.

Қатынасты алгоритмдер

Бұған байланысты проблемаларға шамамен реттеу (қажетті реттіліктен белгілі бір дәрежеде ауытқуға дейін реттеу), ішінара реттеу (тізімнің k ең кіші элементтерін ғана реттеу немесе k ең кіші элементтерді табу, бірақ оларды реттелмеген күйде қалдыру) және таңдау (к-шы ең кіші элементті анықтау) жатады. Бұларды толық сұрыптау арқылы тиімсіздікпен шешуге болады, бірақ тиімдірек алгоритмдер де бар, олар көбінесе сұрыптау алгоритмін жалпылау арқылы туындайды. Ең танымал мысал – quicksort алгоритмімен байланысты QuickSelect. Керісінше, кейбір сұрыптау алгоритмдерін таңдау алгоритмін қайталап қолдану арқылы жасауға болады; quicksort және quickselect бірдей айналымдық операция ретінде қарастырылуы мүмкін, олардың айырмашылығы тек екі жаққа (quicksort, бөліп талқандау) немесе бір жаққа (quickselect, қысқарту және талқандау) рекурсия жасауда ғана. Сорттау алгоритмінің керісі – араластыру алгоритмі. Бұл екеуі түбірінен өзгеше, себебі араластыру үшін кездейсоқ сандардың көзі қажет. Араластыруды сұрыптау алгоритмі арқылы да іске асыруға болады, атап айтқанда, кездейсоқ сұрыптау арқылы: тізімнің әрбір элементіне кездейсоқ сан тағайындалып, содан кейін осы сандар бойынша сұрыптау жасалады. Бірақ бұл тәжірибеде көбінесе қолданылмайды, ал араластыру үшін жақсы белгілі, қарапайым және тиімді алгоритм бар: Фишер–Яйтс араластыруы. Сорттау алгоритмдері көп жағдайда тәртіп табу үшін тиімсіз болады. Әдетте, элементтердің салыстыруға болатын сенімді функциясы болмағанда (мысалы, дауыс беру жүйелері сияқты, көпшілік пікірінен алынған таңдаулар), салыстырулар өте қымбат болғанда (спорт) немесе барлық критерийлер бойынша барлық элементтерді жұптап салыстыру мүмкін болмағанда (іздеу жүйелері). Мұндай жағдайларда мәселе көбінесе рейтинг деп аталады, ал мақсат – салыстырулар немесе рейтингтерден алынған ықтималдықтарға сәйкес белгілі бір критерий бойынша "ең жақсы" нәтижені табу. Мысалы, шахматта ойыншылар Elo рейтингтік жүйесімен бағаланады, ал рейтингтер сұрыптау алгоритміне емес, турнирлік жүйе арқылы анықталады.