Кіріспе

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

Коктейльді шайқағыш сұрыптау, сонымен қатар екі бағытты көпіршік сұрыптау, коктейль сұрыптау, шайқағыш сұрыптау (бұл таңдау сұрыптаудың түріне де сілтеме жасай алады), толқынды сұрыптау, араластыру сұрыптау немесе шаттл сұрыптау – бұл көпіршік сұрыптаудың кеңейтілген түрі. Алгоритм екі бағытта жұмыс істеу арқылы көпіршік сұрыптауды кеңейтеді. Ол тізімнің басына элементтерді жылдам жылжыту арқылы көпіршік сұрыптауға қарағанда жақсырақ болғанымен, өнімділіктің айтарлықтай жақсаруын қамтамасыз етпейді. Көптеген көпіршік сұрыптау түсіндірмелері сияқты, коктейльді шайқағыш сұрыптау негізінен оқу құралы ретінде қолданылады. Python және Java сияқты танымал бағдарламалау тілдеріне енгізілген сұрыптау кітапханаларында quicksort, merge sort немесе timsort сияқты тиімді алгоритмдер қолданылады.

Бұзықпен сұрыптаудан айырмашылықтары

Коктейль шайқағыш сұрыптау – көпіршік сұрыптаудың шағын өзгеруі. Ол тізімді төменнен жоғарыға қарай қайта-қайта өтудің орнына, төменнен жоғарыға және содан кейін жоғарыдан төменге кезекпен өтуімен ерекшеленеді. Бұл стандартты көпіршік сұрыптауға қарағанда сәл жақсы нәтиже беруі мүмкін. Мұның себебі – көпіршік сұрыптау тізімді тек бір бағытта өтеді және демек, әр итерацияда элементтерді бір қадамға ғана артқа жылжыта алады. Бұл пікірді дәлелдейтін тізім мысалы – (2,3,4,5,1) тізімі, ол сұрыпталған болу үшін коктейль шайқағыш сұрыптаудан бір рет өтуі жеткілікті, ал өсуге бағытталған көпіршік сұрыптауды қолданса, төрт рет өтуі керек болады. Дегенмен, коктейль шайқағыш сұрыптаудың бір өтуі екі көпіршік сұрыптау өтуіне тең деп есептеледі. Әдетте, коктейль шайқағыш сұрыптау көпіршік сұрыптаудан екі есеге жуық жылдам. Тағы бір оңтайландыру – алгоритм соңғы нақты алмасу қайда жасалғанын есте сақтауы мүмкін. Келесі итерацияда бұл шектен тыс алмасулар болмайды және алгоритм қысқа өтулер жасайды. Коктейль шайқағыш сұрыптау екі бағытта жүргендіктен, сынақтан өтетін алмасу диапазоны әр өтуде тарылады, демек, жалпы орындалу уақыты сәл қысқарады.

Күрделілігі

Үлкен О нотациясы бойынша коктейль шайқағыш сұрыптаудың күрделілігі нашар жағдай мен орташа жағдай үшін де , бірақ сұрыптау алгоритмін қолданғанға дейін тізім көбінесе реттелген болса, ол жақындап келеді. Мысалы, егер әрбір элемент соңғы орнынан k (k ≥ 1) қадамдай ғана алшақ болса, коктейль шайқағыш сұрыптаудың күрделілігі болады. Коктейль шайқағыш сұрыптау туралы "Компьютерлік бағдарламалау өнері" кітабында қысқаша айтылады, сондай-ақ бұршақ сұрыптаудың ұқсас жетілдірілген түрлері де қарастырылады. Қорытындылай келе, Кнут бұршақ сұрыптау және оның жақсартулары туралы былай дейді: