Hitro razvrščanje kot programska metoda

Leta 1960 je K. A. Hoare razvil metodo za hitro razvrščanje informacij, ki so postale najbolj znane. Danes se pogosto uporablja pri načrtovanju, saj ima veliko pozitivnih lastnosti: to se lahko uporablja za splošne primere, ki jih potrebuje majhno povečanje dodatnega pomnilnika, ki je združljiva z različnimi vrstami seznamov in enostavno izvajati. Vendar pa obstajajo tudi slabosti, ki ima hitro urejanje: z delom dovoljeno veliko napak, in je nekoliko nestabilen.

Vendar je to najbolj raziskana različica. Po pojavu Hoarovih prvih izračunih se je veliko ukvarjalo z njeno gosto študijo. Na teoretičnih vprašanjih iskanja časa, porabljenega za delo, je bilo ustvarjeno veliko bazo, ki so ga podpirali empirični podatki. Pripravili so resnične predloge za izboljšanje glavnega algoritma in povečanje hitrosti dela.

Hitro razvrščanje je zelo pogosto, ga je mogoče najti povsod. Temelji na metodi TList.Sort, ki obstaja v vseh različicah (razen v 1) Delphija, knjižnični funkciji porabljenega časa, qsort v C + +.

Osnovno načelo dela je mogoče oblikovati kot "razdeliti in osvojiti". Razčlenitev seznama je razdeljena v dve skupini in sortiranje se izvede za vsak del posebej. Iz tega sledi, da je treba več pozornosti nameniti postopku ločevanja, v katerem se zgodi naslednje: se določi osnovni element in je relativno preuredili svoj celoten seznam. Vgrajen na levi strani skupine kandidatov, katerih vrednost je nižja od vseh drugih predpisov za prenos. Izkazalo se je, da je glavni element na razvrščenem seznamu na svojem mestu. Naslednja faza - izziv rekurzivne sortiranja funkcije obeh straneh elementov glede na podlago. Proces dela se konča le, če seznam vsebuje le en element, to je, da bo razvrščen. Tako, da bi obvladali funkcijo programskega kot hiter vrste, je treba vedeti, delo algoritmov na nižji ravni: a) izbiranje osnovni elementa- b) najbolj učinkovit permutacije seznama za dva niza z manjšimi in večjimi vrednostmi.

Seznanili se bomo z načeli prvega. Pri izbiri osnovnega elementa bi bilo najbolje izbrati srednji del s seznama. Potem, ko je zlomljen, je razdeljen na dve enaki polovici. Izračunajte samo povprečna vrednost na seznamu je zelo težko, tako da tudi najhitrejše sortiranje obide ta račun ob strani. Toda izbira glavnega elementa z največjo ali najnižjo vrednostjo tudi ni najboljša možnost. V primeru takšne definicije bo zagotovljeno, da bo eden od ustvarjenih seznamov prazen, drugi pa popoln. Zato sklepamo, da bi kot osnovni element morali izbrati tistega, ki je bližje povprečju, vendar nadalje od najvišje in najmanjše.

Ko se odločite za izbiro, lahko nadaljujete z delovanjem algoritma deljenja. To so tako imenovani notranji cikli hitrosti. Vse je zgrajeno na dveh hitro delujočih indeksih: prvi bo šel po elementih od leve proti desni, drugi pa, nasprotno, od desne proti levi. Začne se izvršitveni postopek na desni: indeks gre skozi seznam in primerja vse vrednosti z glavnim. Cikel se šteje za popoln, če je element manjši ali enak osnovnemu. To pomeni, da se vrednost indeksa primerja in zmanjša. Na levi strani je delo končano, ko najdete večjo ali enako vrednost. In tu se vrednost primerjave poveča.

Na tej stopnji algoritma deljenja, ki vsebuje hitro sortiranje, se lahko pojavita dve situaciji. Prvi je, da bo indeks na levi manj kot desno. To označuje napako, to pomeni, da so elementi, na katere je bil določen, na seznamu v napačnem vrstnem redu. Izhod je spreminjanje mest. Druga situacija je, ko sta oba stolpca enaka ali presečena. To kaže na uspešno razdelitev seznama, to pomeni, da je delo mogoče šteti za popolno.