Кіріспе

Сорталау алгоритмі

Шелек сұрыптау, немесе қоқыс сұрыптау – массив элементтерін бірнеше шелекке тарату арқылы жұмыс істейтін сұрыптау алгоритмі. Әрбір шелек жеке-жеке сұрыпталады, басқа сұрыптау алгоритмін қолдану арқылы немесе шелек сұрыптау алгоритмін рекурсивті қолдану арқылы. Бұл тарату сұрыптау, бір шелекке бірнеше кілт рұқсат ететін көгершін ұясы сұрыптауының жалпылануы, және ең маңызды цифрдан ең аз маңызды цифрға қарай радикс сұрыптауының туысы. Шелек сұрыптау салыстырулар арқылы жүзеге асырылуы мүмкін, сондықтан оны салыстыру сұрыптау алгоритмі деп қарастыруға болады. Есептеу күрделілігі әрбір шелекті сұрыптау үшін қолданылатын алгоритмге, қолданылатын шелектердің санына және кіріс деректерінің біркелкі таралуына байланысты. Шелек сұрыптау келесідей жұмыс істейді: Бастапқыда бос "шелектер" массивін құру. Тарату: Бастапқы массивті қарап өтіп, әрбір элементті тиісті шелекке орналастыру. Бос емес әрбір шелекті сұрыптау. Жиналу: Шелектерді ретімен қарап, барлық элементтерді бастапқы массивке қайта орналастыру.

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

Кіріс деректерінде бір-біріне жақын бірнеше кілттер (кластерлеу) болған жағдайда, олардың бірге бір қапшыққа түсуі мүмкін, нәтижесінде кейбір қапшықтарда орташадан көп элемент болады. Ең нашар жағдай, барлық элементтер бір қапшыққа түскенде туындайды. Осы жағдайда жалпы өнімділік әр қапшықты сұрыптау үшін қолданылатын алгоритммен анықталады, мысалы, енгізу сұрыптау немесе салыстыру сұрыптау алгоритмдері, мәселен, біріктіру сұрыптау.

Жалпы топтастыру

Бакеттік сұрыптаудың ең көп қолданылатын түрі нөл мен ең жоғары мән М арасындағы n сандық кіріс тізімімен жұмыс істейді және мән диапазонын әрқайсысы M/n өлшемді n бакетке бөледі. Егер әр бакет кіріктіру сұрыптауын қолданып сұрыпталса, онда сұрыптаудың күтілетін сызықтық уақытта орындалатыны дәлелденеді (мұнда орташа есеп барлық мүмкін кірістер бойынша алынады). Дегенмен, бұл сұрыптаудың тиімділігі кластерлену кезінде төмендейді; егер көптеген мәндер бір-біріне жақын орналасса, олардың бәрі бір бакетке түсіп, баяу сұрыпталады. Бастапқы бакеттік сұрыптау алгоритмі кіріс элементтерінің [0,1) аралығында біркелкі таратылатын кездейсоқ процесс арқылы жасалатынын болжайды, осылайша бұл тиімділік төмендеуінің алдын алады.

ProxmapSort (жауапты түрде)

Жоғарыда сипатталған қарапайым букет сұрыптауға ұқсас, ProxmapSort кілттер массивін кілттердің ішінара ретін сақтайтын "карта кілті" функциясы арқылы кіші массивтерге бөлу арқылы жұмыс істейді. Әрбір кілт кіші массивіне қосылғанда, енгізу сұрыптау осы кіші массивті реттеу үшін қолданылады, нәтижесінде ProxmapSort аяқталған кезде бүкіл массив реттелген күйде болады. ProxmapSort букет сұрыптаудан карта кілтін пайдаланып деректерді реттелген тізімдегі орнына жуық орналастыру арқылы ерекшеленеді, соның нәтижесінде кілттердің "proxmap" – жақындық картасы құрылады.

Гистограмманы сұрыптау

Бакет сұрыптаудың гистограммалық сұрыптау немесе санау сұрыптау деп аталатын тағы бір түрі, әр бакетке түсетін элементтердің санын санау массивін пайдаланып есептейтін алғашқы кезеңді қосады. Осы ақпаратты қолданып, массивтік мәндерді орын алмастырулар тізбегі арқылы тікелей бакеттерге орналастыруға болады, бакеттерді сақтауға қосымша орын қажет етілмейді.

Пошташының түрі

Пошташының сұрыптау – элементтердің иерархиялық құрылымын пайдаланатын, әдетте атрибуттар жиынтығымен сипатталатын, шелек сұрыптаудың бір түрі. Бұл алгоритм пошта бөлімдеріндегі хаттарды сұрыптау машиналарында қолданылады: хаттар ең алдымен ішкі және халықаралық жіберілгендерге бөлінеді; содан кейін штатқа, провинцияға немесе аумаққа; одан кейін межелі пошта бөлімшесіне; содан кейін маршруттарға және т.б. түйіндемелер бір-бірімен салыстырылмағандықтан, сұрыптау уақыты O(cn) құрайды, мұнда c түйіндеменің мөлшеріне және шелектердің санына байланысты. Бұл «жоғарыдан төменге» немесе «ең маңызды цифрден бастап» жұмыс істейтін радикс сұрыптауға ұқсас.

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

Шаттастыру сұрыптау – бұл n элементтің бірінші 1/8 бөлігін алып тастаудан басталатын, оларды рекурсивті түрде сұрыптап, массивке орналастыру арқылы жүзеге асырылатын шелек сұрыптаудың бір түрі. Бұл n/8 "шелекті" құрайды, оларға қалған 7/8 элемент таралды. Әрбір "шелек" содан кейін сұрыпталады, ал "шелектер" сұрыпталған массивке біріктіріледі.

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

Сауытпен сұрыптауды санау сұрыптаудың жалпылауы ретінде қарастыруға болады; шын мәнінде, егер әрбір сауыттың мөлшері 1 болса, сауытпен сұрыптау санау сұрыптауға дейін төмендейді. Сауытпен сұрыптаудың өзгермелі сауыт мөлшері оған O(n) жадты пайдалануға мүмкіндік береді, O(M) жадты пайдаланудың орнына, мұнда M – ерекше мәндердің саны; мұның орнына, ол санау сұрыптаудың O(n + M) ең нашар жағдай көрсеткішінен бас тартады. Екі сауытты сауытпен сұрыптау – жылдам сұрыптаудың бір түрі, онда півот мәні әрқашан мән диапазонының ортаңғы мәні ретінде таңдалады. Бұл таңдау біркелкі таратылған деректер үшін тиімді болғанымен, жылдам сұрыптауда півотты таңдаудың басқа әдістері, мысалы, кездейсоқ таңдалған півоттар, деректер үлестірілімінде кластерленуге қарсы тұруды жақсартады. n-жолды біріктіру сұрыптау алгоритмі тізімді n кіші тізімге бөлуден және әрқайсысын сұрыптаудан басталады; алайда, біріктіру сұрыптау арқылы жасалған кіші тізімдердің мәндер диапазондары үстіне түседі, сондықтан оларды сауытпен сұрыптаудағыдай қарапайым тізбектеу арқылы қайта құрастыруға болмайды. Оның орнына, оларды біріктіру алгоритмімен араластыру қажет. Дегенмен, бұл қосымша шығындар қарапайым тарату фазасымен және әрбір кіші тізімнің бірдей мөлшерде болуын қамтамасыз ету мүмкіндігімен өтелуі мүмкін, бұл ең нашар жағдайда жақсы уақыт шегін қамтамасыз етеді. Жоғарыдан төмен радикс сұрыптауды сауытпен сұрыптаудың ерекше жағдайы ретінде қарастыруға болады, онда мәндер диапазоны мен сауыттар саны екінің дәрежесімен шектеледі. Осылайша, әрбір сауыттың мөлшері де екінің дәрежесі болады және процедура рекурсивті түрде қолданылуы мүмкін. Бұл тәсіл тарату фазасын үдетуге мүмкіндік береді, өйткені сауытын анықтау үшін әр элементтің биттік өрнегінің тек алғашқы бөлігін қарау жеткілікті.