Quicksort programazio metodo gisa

1960an, K. A. hoar metodo bat garatu informazioaren azkarrak ordenazio egiteko, ospetsuena bihurtu zen. Gaur egun oso zabalduta programazio erabiltzen da, ezaugarri positibo asko duelako: kasu orokorrerako erabil daiteke, memoria gehigarria gehikuntza txiki bat, zerrendak mota desberdinak bateragarriak eta erraza ezartzea eskatzen du. Baina badira eragozpenak, ditu Quicksort: erabilita lan akats asko onartzen, eta zertxobait ezegonkorra da.

Hala ere, gehien ikasi bertsioan da. Lehenengo ordainketa Hoare ostean, askok bere ikasketa trinko egin. base handiak lana, hau da froga enpirikoak oinarritu gastatu denbora aurkitzeko galdera teorikoak ezarri zen. Baziren oinarrizko algoritmoa eta abiadura handitu hobetzeko benetako proposamenak.

Quicksort oso ohikoa da, nonahi aurki daitezke. Bere oinarria On metodoa inplementatu TList.Sort, bertsio guztiak (salbu 1) Delphi, liburutegia denboraren funtzioa, osatzeko C qsort ++ hartu presente.

Eragiketa oinarrizko printzipioa izango da "Banatu eta agindu" gisa formulatu daiteke. Zerrendako hautsi gertatzen da bi taldetan, eta berak parte bakoitzeko ordenatuta. dago oinarrian elementu bat zehaztuko ditu eta nahiko berrantolatu zuen bere zerrenda osoa: arreta gehiago da bereizketa prozesua, horretan honako hau gertatzen ordaindu beharko jarraitzen du. hautagaiak talde baten ezkerrean eraikia, balio horietatik beste transferentzia arau guztiak baino txikiagoa da. Bihurtzen da ordenatuko zerrendan elementu nagusia bere lekua dago. Hurrengo etapa - a erronka errekurtsiboak ordenazio bi elementu oinarri erlatiboa aldeetatik funtzioak. prozesuan lan egiten du zerrendako elementu bat bakarrik badu soilik amaitzen da, hau da ordenatuko. Hortaz, programazio funtzio bat moduko azkar bat bezala menderatzea ere, beharrezkoa da behe-mailako algoritmoak lana ezagutu: a) oinarri kidea aukeratu du; b) permutazio eraginkorrena zerrenda balioak txikiagoak eta handiagoak dituzten bi multzo ekoizteko.

lehen printzipioak ezagutzea. Noiz base kidea aukeratzerakoan, haien egon besteko zerrendatik aukeratu ditu. Ondoren atsedenaldian bi zati berdinetan banatzen da. Just kalkulatzeko batez besteko balioa zerrendan oso zaila da, beraz, nahiz eta ordenazio azkarrena kalkulu alde honetan inguratzen. Baina gehieneko edo gutxieneko balioa oinarrizko elementua aukeraketa - ere ez da aukerarik onena. kasuan inork determinazio hala nola sortzen zerrendak Hutsik bermatu egingo da, eta bigarrena osoa. Hori dela ondorioztatu base kidea gisa bat dela batez besteko hurbilago aukeratu behar dira, baina gehienezko eta gutxieneko orrian.

Behin aukera bat zehazten da, deskonposizio algoritmoa jarraitu ahal izango duzu. Hau barruko begiztak deiturikoak azkar moduko. Dena bi Rapid Access indizeak gainean eraikia dago: ezkerretik eskuinera, bigarrenean arte, aitzitik elementuen gainean lehen joateko, ezkerretik eskuinera. Eragiketa exekuzioa eskuineko Hasiera: indizean zerrendan dago eta balioen alderatu nagusia da. Zikloa amaitutakoan denean elementu baino txikiagoa edo berdina oinarri da. Hau da, ez dago konparazio bat da eta indizearen balioa gutxitzen. On ezkerreko denean lana da baino edo balio bereko handiagoa amaitu. Hemen, konparazio balio handitzen.

partitzea algoritmoa bertan quicksort osatzen Etapa honetan, bi egoera sor daitezkeen. Lehenengoa da ezkerrean indizean duten eskubidea baino txikiagoa da. Honek arazoak adierazten du, ondoren, ez dira horren gainean zerrendako zen adierazi elementu okerreko ordenean daude. Irteera - beren lekuak aldatu. Bigarren egoera da noiz zutabean, bai da berdina edo zeharkatu. Hau zerrendako bereizketa arrakasta adierazten du, hau da, lana amaitu da.