Мұқтарлы сорту әдісі немесе бұршақ сорту алгоритмі
Bead sort
Бұйық сұрыптау (Bead Sort): 2002 ж. жасалған, жағылған бұйықтар арқылы сандарды сұрыптау алгоритмі. Оның тиімділігі, қолданылу шектеулері туралы біліңіз.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Бисер сұрыптау, сондай-ақ гравитациялық сұрыптау деп аталады, бұл табиғи сұрыптау алгоритмі. Оны 2002 жылы Джошуа Дж. Аруландам, Кристиан С. Калуде және Майкл Дж. Диннен жасап, Теориялық компьютерлік ғылымдар жөніндегі Еуропалық қауымдастықтың бюллетенінде жариялаған. Бисер сұрыптаудың цифрлік және аналогтық аппараттық іске асырылымдары O(n) сұрыптау уақытына қол жеткізе алады; алайда, бұл алгоритмнің бағдарламалық қамтамасында іске асырылуы айтарлықтай баяу болады және тек оң бүтін сандар тізімін сұрыптау үшін ғана қолданылуы мүмкін. Бұған қоса, ең жақсы жағдайда да алгоритмге O(n²) жад кеңістігі қажет болып көрінеді.
Bead sort, also called gravity sort, is a natural sorting algorithm, developed by Joshua J. Arulanandham, Cristian S. Calude and Michael J. Dinneen in 2002, and published in The Bulletin of the European Association for Theoretical Computer Science. Both digital and analog hardware implementations of bead sort can achieve a sorting time of O(n); however, the implementation of this algorithm tends to be significantly slower in software and can only be used to sort lists of positive integers. Also, it would seem that even in the best case, the algorithm requires O(n2) space.
Алгоритмнің жалпы көрінісі
Бұл әрекетті, мысалы, абакустағы дөңгелектердің параллель тіреулерде сырғанауына ұқсатуға болады. Дегенмен, әр тіреуде әртүрлі мөлшерде дөңгелек болуы мүмкін. Бастапқыда, дөңгелектерді тік тіреулерге ілінгендей елестету пайдалы. 1-қадамда, n=5 қатар дөңгелектер m=4 тік тіреулерде осылай орналасқан. Әр қатардың оң жағындағы сандар сол қатарды көрсететін мәнді білдіреді; 1- және 2-қатарлар 3 оң бүтін санын көрсетеді (өйткені олардың әрқайсысында үш дөңгелек бар), ал жоғарғы қатар 2 оң бүтін санын көрсетеді (себебі онда тек екі дөңгелек бар). Егер дөңгелектерді түсірсек, қатарлар сұрыпталған түрде бірдей бүтін сандарды көрсетеді. 1-қатар жиынның ең үлкен санын, ал n-қатар ең кішкене санын қамтиды. Егер 1 k тіреулерде дөңгелектер тізбегін қамтитын және k+1 m тіреулерді бос қалдыратын жоғарыда аталған келісім сақталса, онда да солай болады. Физикалық мысалдағы дөңгелектердің "түсуіне" рұқсат ету, жоғары қатарлардағы үлкен мәндердің төменгі қатарларға таралуына мүмкіндік берді. Егер a қатарындағы мән a+1 қатарындағы мәннен кіші болса, a+1 қатарындағы бірнеше дөңгелек a қатарына түседі; бұл міндетті түрде болады, өйткені a қатарында a+1 қатарынан түсетін дөңгелектерді тоқтатуға дөңгелектер жоқ. Дөңгелектерді сұрыптау механизмі санау сұрыптау механизміне ұқсас; әр тіректегі дөңгелектердің саны сол тіреу индексіне тең немесе одан үлкен мәнді элементтердің санына сәйкес келеді.
The bead sort operation can be compared to the manner in which beads slide on parallel poles, such as on an abacus. However, each pole may have a distinct number of beads. Initially, it may be helpful to imagine the beads suspended on vertical poles. In Step 1, such an arrangement is displayed using n=5 rows of beads on m=4 vertical poles. The numbers to the right of each row indicate the number that the row in question represents; rows 1 and 2 are representing the positive integer 3 (because they each contain three beads) while the top row represents the positive integer 2 (as it only contains two beads). If we then allow the beads to fall, the rows now represent the same integers in sorted order. Row 1 contains the largest number in the set, while row n contains the smallest. If the above mentioned convention of rows containing a series of beads on poles 1 k and leaving poles k+1 m empty has been followed, it will continue to be the case here. The action of allowing the beads to "fall" in our physical example has allowed the larger values from the higher rows to propagate to the lower rows. If the value represented by row a is smaller than the value contained in row a+1, some of the beads from row a+1 will fall into row a; this is certain to happen, as row a does not contain beads in those positions to stop the beads from row a+1 from falling. The mechanism underlying bead sort is similar to that behind counting sort; the number of beads on each pole corresponds to the number of elements with value equal or greater than the index of that pole.