Бағдарламалау әдісі ретінде Quicksort

1960 жылы, Қ А Hoar ең танымал болды, ақпаратты тез Сұрыптауға әдісі әзірленді. ол оң қасиеттерін көп Бүгінде ол кеңінен, бағдарламалау қолданылады: ол жалпы жағдайларды пайдалануға болады, ол тізімдер мен іске асыру оңай түрлі түрлерімен үйлесімді қосымша жадта шағын арттыру, талап етеді. Бірақ Quicksort бар кемшіліктер бар: пайдаланып жұмыс қателіктер көп рұқсат, және ол бірнеше тұрақсыз болып табылады.

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

Quicksort ол барлық жерде табуға болады, өте қарапайым болып табылады. оның негізінде әдісі (1 қоспағанда) барлық нұсқаларында Delphi осы TList.Sort, жүзеге асырылады, уақыт кітапхана функциясы ол, C ++ тілінде qsort аяқтау үшін алды.

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

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

таңдау анықталады кейін, ыдырау алгоритм кірісуге болады. Бұл аталатын ішкі Жылдам сұрыптау ілмектер. Барлығы екі Rapid Access көрсеткіштері бойынша құрылады: бірінші оңнан солға, керісінше, солдан оңға элементтері секундтағы өтіңіз. операция орындау құқығы басталады: индекс тізімінде болып табылады және негізгі барлық мәндерін салыстыру. элементі аз немесе базалық тең болған кезде цикл аяқталған. Яғни, бар салыстыру болып табылады және индекс мәнін азайтады. сол жағынан жұмыс үлкен немесе тең мәні аяқталған кезде. Мұнда, салыстыру мәні артады.

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