Smoothsort алгоритмі: салыстыру негізіндегі сұрыптау әдісі
Smoothsort
Smoothsort алгоритмі: компьютерлік ғылымдағы салыстыру негізіндегі тиімді реттеу әдісі. Heapsort-тан жақсы, жартылай реттелген деректерде жылдам жұмыс істейді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Салыстыруға негізделген сұрыптау алгоритмі
Comparison based sorting algorithm
Компьютерлік ғылымда, smoothsort – салыстыруға негізделген сұрыптау алгоритмі. Heapsort-тың бір түрі, ол 1981 жылы Эдсгер Дийкстрамен ойлап табылып жарияланды. Heapsort сияқты, smoothsort – орнында орындалатын алгоритм және үлкен O белгісімен операциялардың жоғарғы шегі бар, бірақ ол тұрақты сұрыптау емес. Smoothsort-тың артықшылығы – егер кіріс деректер қандай да бір деңгейде сұрыпталған болса, ол O(n) уақытына жақындайды, ал heapsort бастапқы сұрыпталған күйіне қарамастан O(n log n) орташа уақытты қажет етеді.
In computer science, smoothsort is a comparison based sorting algorithm. A variant of heapsort, it was invented and published by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in place algorithm with an upper bound of [[Big O notation operations (see big O notation), but it is not a stable sort. The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state.
Төменге қарай сырып алу
Негізгі сырғанау операциясы (Дайкстра "триккл" деп атайды) үйінді инвариантын тек тамыр түйінінде бұзылу мүмкін болған жағдайда қалпына келтіреді. Егер тамыр түйіні өзінің кез келген баласынан кіші болса, ол ең үлкен баласымен ауыстырылады және процесс жаңа кіші ағашта тамыр түйінімен қайталанады. Smoothsort пен бинарлық максималдық үйінді арасындағы айырмашылық – әрбір созылудың тамыры үшінші "қадамбалы" бойынша реттелуі керек: алдыңғы созылудың тамыры. Сондықтан төмен қарай сырғанау процедурасы төрттік салыстырулар сериясынан басталады (тамыр түйіні және үш баласы), қадамбалы максималды элемент болмайынша, содан кейін үштік салыстырулар сериясынан басталады (тамыр және екі баласы), тамыр түйіні өзінің соңғы орнын тауып, инварианттар қайта орнатылғанша. Әрбір ағаш толық екілік ағаш: әрбір түйінде екі баласы болады немесе баласы жоқ. Стандартты жасырын бинарлық үйіндіде кездесетін бір баланың ерекше жағдайымен айналысудың қажеті жоқ. (Бірақ қадамбалы байланыстардың ерекше жағдайы осы үнемдеуді толықтырады.) O(log n) созылулар бар, олардың әрқайсысы O(log n) тереңдігіндегі ағаш болып табылады, сондықтан әрбір сырғанау операциясын орындау уақыты O(log n) арқылы шектеледі.
The core sift down operation (which Dijkstra calls "trinkle") restores the heap invariant when it is possibly violated only at the root node. If the root node is less than any of its children, it is swapped with its greatest child and the process repeated with the root node in its new subtree. The difference between smoothsort and a binary max heap is that the root of each stretch must be ordered with respect to a third "stepson": the root of the preceding stretch. So the sift down procedure starts with a series of four way comparisons (the root node and three children) until the stepson is not the maximal element, then a series of three way comparisons (the root plus two children) until the root node finds its final home and the invariants are re established. Each tree is a full binary tree: each node has two children or none. There is no need to deal with the special case of one child which occurs in a standard implicit binary heap. (But the special case of stepson links more than makes up for this saving.) Because there are O(log n) stretches, each of which is a tree of depth O(log n), the time to perform each sifting down operation is bounded by O(log n).
Оң жаққа элементті қосу арқылы үйме аймағын кеңейту
Қосымша элемент созылулар тізбегіне (бір-біріне қосылмаған үйме құрылымдарының тізімі) қосылғанда, ол жаңа бір элементтік созылу құрайды немесе екі оң жақ созылуды біріктіріп, олардың екі түбіріне ата-ана болып, тізбекте оларды алмастыратын жаңа созылу құрайды. Қай жағдай орын алатыны тек қазіргі созылулардың мөлшеріне (және соңында қосылған элементтің индексіне) байланысты. Дийкстра созылулардың мөлшері L(k+1) және L(k) болған жағдайда ғана біріктіріледі деп көрсетті, яғни, екі тізбектелген Леонардо саны болғанда; жаңа созылудың мөлшері L(k+2) болады. Екі жағдайда да, жаңа элемент үйме құрылымындағы дұрыс орнына ие болу үшін төменге сұрыпталуы керек. Жаңа түйін бір элементтік созылу болса да, ол алдыңғы созылудың түбірімен салыстырылып сұрыпталуы тиіс.
When an additional element is considered for incorporation into the sequence of stretches (list of disjoint heap structures) it either forms a new one element stretch, or it combines the two rightmost stretches by becoming the parent of both their roots and forming a new stretch that replaces the two in the sequence. Which of the two happens depends only on the sizes of the stretches currently present (and ultimately only on the index of the element added); Dijkstra stipulated that stretches are combined if and only if their sizes are L(k+1) and L(k) for some k, i. e., consecutive Leonardo numbers; the new stretch will have size L(k+2). In either case, the new element must be sifted down to its correct place in the heap structure. Even if the new node is a one element stretch, it must still be sorted relative to the preceding stretch's root.
Оңтайландыру
Дикстраның алгоритмі толық үйінді инварианты өсу кезеңінің соңында ғана қажет екенін байқау арқылы жұмысты үнемдейді, бірақ ол әрбір аралық қадамда қажет емес. Атап айтқанда, элементтің баласынан үлкен болуы талабы тек соңғы ағаш түбірлері үшін ғана маңызды. Сондықтан, элемент қосылғанда, оның болашақ ата-анасының орнын анықтаңыз. Егер ол сұрыпталуға тиіс қалған мәндер диапазонында болса, баласы жоқ деп есептеп, тек ағымдағы ағаш ішінде ғана сұрыптауды жүргізіңіз.
Dijkstra's algorithm saves work by observing that the full heap invariant is required at the end of the growing phase, but it is not required at every intermediate step. In particular, the requirement that an element be greater than its stepson is only important for the elements which are the final tree roots. Therefore, when an element is added, compute the position of its future parent. If this is within the range of remaining values to be sorted, act as if there is no stepson and only sift down within the current tree.
Басты элементті оң жақтан алып тастау арқылы үйінді аймағын кішірейту
Бұл кезеңде созылулар тізбегінің пішіні өсу кезеңінің өзгерістерін кері бағытта қайталайды. Жапырақ түйінін бөліп шығару кезінде ешқандай жұмыс қажет емес, бірақ жапырақ емес түйін үшін оның екі баласы жаңа созылулардың түбірлеріне айналады және созылулардың түбірлері тізбегіндегі дұрыс орнына жылжытылуы керек. Бұл екі рет төмен қарай икемдеу арқылы жүзеге асырылады: бірінші сол бала үшін, содан кейін оң бала үшін (оның балама баласы сол бала болған). Толық екілік ағаштағы түйіндердің жартысы жапырақтар болғандықтан, бұл орташа есеппен әр түйін үшін бір рет төмен қарай икемдеу операциясын орындауға мүмкіндік береді.
During this phase, the form of the sequence of stretches goes through the changes of the growing phase in reverse. No work at all is needed when separating off a leaf node, but for a non leaf node its two children become roots of new stretches, and need to be moved to their proper place in the sequence of roots of stretches. This can be obtained by applying sift down twice: first for the left child, and then for the right child (whose stepson was the left child). Because half of all nodes in a full binary tree are leaves, this performs an average of one sift down operation per node.
Оңтайландыру
Жаңа ашылған тамырлардың қалыпты балаларына қатысты дұрыс реттелгендігі белгілі, дау тек олардың өгей балаларына қатысты реттілігі туралы. Сондықтан, үйіндіні қысқарту кезінде, төмен қарай іріктеудің алғашқы қадамын өгей баламен бір салыстыру арқылы жеңілдетуге болады. Егер алмасу болса, келесі қадамдарда толық төрт тармақты салыстыру қажет.
It is already known that the newly exposed roots are correctly ordered with respect to their normal children; it is only the ordering relative to their stepsons which is in question. Therefore, while shrinking the heap, the first step of sifting down can be simplified to a single comparison with the stepson. If a swap occurs, subsequent steps must do the full four way comparison.
Талдау
Smoothsort алдын ала сұрыпталған массивті өңдеуге O(n) уақыт алады, ең нашар жағдайда O(n log n) уақыт алады және көптеген дерлік сұрыпталған кірістерде линейлік өнімділікке жетеді. Дегенмен, ол барлық дерлік сұрыпталған тізбектерді оңтайлы түрде өңдемейді. Ретсіздіктің өлшемі ретінде инверсиялар санын пайдалану (i < j және A[i] > A[j] болатын индекс жұптарының саны; кездейсоқ сұрыпталған кіріс үшін бұл шамамен n²/4), O(n log n) инверсиясы бар кіріс тізбектері болуы мүмкін, бұл оған Ω(n log n) уақыт алуға себеп болады, ал басқа бейімделмелі сұрыптау алгоритмдері осы жағдайларды O(n log log n) уақытында шеше алады. Smoothsort алгоритмі Леонардо үйірмесіндегі барлық ағаштардың өлшемдерін жадында сақтауға қабілетті болуы керек. Олар рет бойынша сұрыпталғандықтан және барлық реттер ерекше болғандықтан, бұл әдетте қандай реттердің бар екенін көрсететін бит векторы арқылы жасалады. Сонымен қатар, ең үлкен рет ең көп дегенде O(log n) болғандықтан, бұл биттерді O(1) машиналық сөздермен кодтауға болады, трансдихотомиялық машиналық модельді қабылдап. O(1) машиналық сөздері бір машиналық сөзбен бірдей емес екенін ескеріңіз. 32 биттік вектор 1=L(32) = 7049155-тен кіші өлшемдер үшін ғана жеткілікті. 64 биттік вектор 1=L(64) = 34335360355129 ≈ 2⁴⁵-тен кіші өлшемдер үшін қолданылады. Жалпы, бұл 1/log₂([[Алтын қатынас векторының биттері өлшемнің бір бітіне.
Smoothsort takes O(n) time to process a presorted array, O(n log n) in the worst case, and achieves nearly linear performance on many nearly sorted inputs. However, it does not handle all nearly sorted sequences optimally. Using the count of inversions as a measure of un sortedness (the number of pairs of indices i and j with i < j and A[i] > A[j]; for randomly sorted input this is approximately n^(2)/4), there are possible input sequences with O(n log n) inversions which cause it to take Ω(n log n) time, whereas other adaptive sorting algorithms can solve these cases in O(n log log n) time. The smoothsort algorithm needs to be able to hold in memory the sizes of all of the trees in the Leonardo heap. Since they are sorted by order and all orders are distinct, this is usually done using a bit vector indicating which orders are present. Moreover, since the largest order is at most O(log n), these bits can be encoded in O(1) machine words, assuming a transdichotomous machine model. Note that O(1) machine words is not the same thing as one machine word. A 32 bit vector would only suffice for sizes less than 1=L(32) = 7049155. A 64 bit vector will do for sizes less than 1=L(64) = 34335360355129 ≈ 2^(45). In general, it takes 1/log2([[Golden ratio bits of vector per bit of size.
Ағаштың сорты
Smoothsort-тен шабыдаланған қарапайым алгоритм – тополь сорты. Голландиялық полидерде жиі кездесетін, көлемі азая беретін ағаштар қатарынан аталған бұл алгоритм, көбінесе сұрыпталмаған деректер үшін smoothsort-тан аз салыстырулар жасайды, бірақ толық сұрыпталған деректер үшін сызықтық уақытқа жете алмайды. Тополь сортының ерекшелігі – әртүрлі ағаштардың тамырлары сұрыпталмайды; оларды бір үйіндіге байланыстыратын "балалық" сілтемелер жоқ. Оның орнына, екінші кезеңде үйінді қысқартылған сайын, ең үлкен элементті табу үшін тамырлар ізделіп қаралады. n қысқару қадамы болғандықтан, олардың әрқайсысы ең үлкенін табу үшін O(log n) тамырды іздеуі керек, сондықтан тополь сортының ең жақсы жағдайдағы орындалу уақыты O(n log n) құрайды. Авторлар Леонардо ағаштарының орнына толық екілік ағаштарды пайдалануды ұсынады, бірақ бұл одан да қарапайым ету үшін жасалған, алайда бұл аз маңызды өзгеріс. Бұл құрылымды жалпы мақсаттағы басымдық кезегі ретінде "кейіннен жүргізілетін үйінді" деп атау ұсынылған, бұл имплицитті биномдық үйіндіге қарағанда қарапайым құрылымда O(1) амортизацияланған енгізу уақытына қол жеткізеді.
A simpler algorithm inspired by smoothsort is poplar sort. Named after the rows of trees of decreasing size often seen in Dutch polders, it performs fewer comparisons than smoothsort for inputs that are not mostly sorted, but cannot achieve linear time for sorted inputs. The significant change made by poplar sort in that the roots of the various trees are not kept in sorted order; there are no "stepson" links tying them together into a single heap. Instead, each time the heap is shrunk in the second phase, the roots are searched to find the maximum entry. Because there are n shrinking steps, each of which must search O(log n) tree roots for the maximum, the best case run time for poplar sort is O(n log n). The authors also suggest using perfect binary trees rather than Leonardo trees to provide further simplification, but this is a less significant change. The same structure has been proposed as a general purpose priority queue under the name post order heap, achieving O(1) amortized insertion time in a structure simpler than an implicit binomial heap.
Қолданбалар
musl C кітапханасы qsort функциясын іске асыру үшін smoothsort алгоритмін пайдаланады.
The musl C library uses smoothsort for its implementation of qsort .