Quicksort kiel programado metodo

En 1960, K. A. Hoar disvolvis metodon por la rapida ordigado de informoj, iĝis la plej fama. Hodiaŭ ĝi estas vaste uzata en programado, kiel havas multajn pozitivaj ecoj: ĝi povas esti uzata por ĝenerala kazoj, ĝi postulas malgrandan pliigon en la aldona memoro, kongrua kun malsamaj tipoj de listoj kaj facile efektivigi. Sed estas malavantaĝoj, kiu havas quicksort: uzante laboro permesis multajn erarojn, kaj tio estas iom malstabila.

Tamen, ĝi estas la plej studita versio. Post la unua pago Hoare, multaj faras lia densa studo. granda bazo estis establita la teoriaj demandoj de trovi la tempo pasigita en la laboro, kiu estas subtenataj de evidenteco empírica. Ekzistis reala proponoj por plibonigi la baza algoritmo kaj pliigita rapido.

Quicksort estas tre komuna, ĝi povas trovi ĉie. Sur ĝia bazo la metodo estas implementado TList.Sort, ĉeestanta en ĉiuj versioj (krom 1) Delphi, la biblioteko funkcio de tempo ĝi prenis por kompletigi, qsort en C ++.

La baza principo de operacio povas esti formulita kiel "dividu kaj regu". Ĝi okazas rompi la liston en du grupojn kaj estas ordo por ĉiu parto de ĝi mem. Sekvas, ke pli da atento devus esti pagita al la procezo de disiĝo, dum kiuj la jenan okazas: estas determinita de bazo elemento kaj ĝi relative rearanĝis sian tutan liston. Enkorpigita maldekstre de grupo de kandidatoj, la valoro de kiu estas pli malgranda ol cxiuj aliaj transigo reguloj. Montriĝas, ke la ĉefa elemento en la ordo listo estas en ĝia laŭrajta loko. La sekva etapo - defio rekursia ordigado funkcioj por ambaŭ flankoj de la elementoj relativa al la bazo. Ĝi finas la procezo funkcias nur se la listo enhavas nur unu elementon, kiun oni devas ordigitaj. Tiel, por majstri programado funkcio kiel rapida speco, estas necese koni la laboron de pli malalta-nivelo algoritmoj: a) la elekto de la bazo membro; b) liston de la plej efika permuto por produkti du aroj kun pli malgrandaj kaj pli grandaj valoroj.

Konatiĝi kun unuaj principoj. Elektinte la bazo membro, devus ideale esti elektitaj el la listo de mezumo. Tiam sur la paŭzo estas dividita en du egalaj duonoj. Nur kalkuli la averaĝa valoro en la listo estas tre malfacila, do eĉ la plej rapida ordigado _bypasses_ tiu kalkulo flanko. Sed la elekto de la baza elemento kun la maksimuma aŭ minimuma valoro - ankaŭ ne la plej bona elekto. En kazo tiu fiksado de unu kreas malplenajn listoj estos garantiita, kaj la dua plena. Pro tio la konkludo, ke kiel la bazo membro devus esti elektita, kiu estas pli proksima al la mezumo, sed la maksimuma kaj minimuma.

Unufoje elekto estas determinita, vi povas daŭrigi per la putriĝo algoritmo. Tiu tiel nomata ena masxojn rapida speco. Ĉio estas konstruita sur du Rapid Aliro indeksoj: unue iri tra la elementoj de maldekstre dekstren, la dua, male, de dekstra al maldekstra. Komencas operacion ekzekuto dekstra: la indekso estas en la listo kaj kompari ĉiuj valoroj al la ĉefa. La ciklo estas kompleta kiam la elemento estas malpli ol aŭ egala al la normala kvanto. Tio estas, estas komparo kaj malpliigas la valoron de la indekso. Maldekstre kiam la laboro estas finita pli granda ol aŭ egala valoro. Ĉi tie, la komparo valoro pliigas.

Je tiu stadio de dispartiganta algoritmo kiu konsistas quicksort, du situacioj povas ekesti. La unua estas ke la indekso maldekstre estas malpli ol dekstre. Tiu indikas eraron, tiam estas eroj sur kiu ĝi estis deklarita en la listo estas en la malĝusta ordo. Eligo - ŝanĝi siajn lokojn. La dua situacio estas kiam ambaŭ de la kolumno estas egala al aŭ transiris. Tiu indikas sukcesan apartigon de la listo, tio estas, la laboro estas nun kompleta.