Quick Sort je ena najboljših metod razvrščanja nizov.

Če programirate in vaša koda presega pisanje kalkulatorja, boste pogosto naleteli na potrebo po razvrščanju določenega niza podatkov. Obstaja veliko načinov za razvrščanje. V tem članku bomo analizirali glavne od njih in se osredotočili na hitro sortiranje.

Hitri razvrstitveni koncept

Hitro razvrščanje - Quick Sort ali qsort. Z imenom postane jasno, kaj je in zakaj. Toda če ni jasno, potem to je algoritem S hitrim razvrščanjem matrike ima algoritem povprečno učinkovitost O (n log n). Kaj to pomeni? To pomeni, da se povprečni čas delovanja algoritma poveča po isti poti kot graf te funkcije. Nekateri priljubljeni jeziki imajo vgrajene knjižnice s tem algoritmom in to že kaže, da je izjemno učinkovito. To so jeziki, kot so Java, C ++, C #.

Algoritem

Metoda hitrega razvrščanja uporablja rekurzijo in strategijo "Divide and Conquer".

1. V matriki iščemo določen podporni element, zaradi enostavnosti je bolje vzeti osrednji element, vendar če želite delati na optimizaciji, boste morali poskusiti različne možnosti.

2. Na levi strani podpore se išče element, ki je večji od sklica, na desni, manjši element kot referenca, nato pa jih zamenjamo. To storite tako dolgo, dokler je maksimalna vrednost na desni manj kot na levi. Tako se vsi majhni elementi vržejo na začetek, veliki - do konca.

3. Ta algoritem rekurzivno uporabite ločeno v levem in desnem delu našega algoritma, nato znova in znova, dokler ne dosežete enega elementa ali določenega števila elementov. Kaj je to število elementov? Obstaja še en način za optimizacijo tega algoritma. Ko razvrščeni del postane približno enak 8 ali 16, ga lahko obdelamo s svojim običajnim razvrščanjem, npr. Zato bomo povečali učinkovitost našega algoritma, saj majhnih nizov ne obdeluje tako hitro, kot bi želeli.

Tako bo celotno polje obdelano in razvrščeno. In zdaj bomo vizualno preučili ta algoritem.

Hitro razvrščanje

Ali je hitro razvrščanje najhitrejši algoritem za sortiranje? Definitivno ne. Zdaj je vedno več sortiranja, v trenutku, ko je najhitrejše sortiranje Timsort, deluje izjemno hitro za matrike, ki so bile prvotno razvrščene drugače. Vendar ne pozabite, da je hitra metoda sortiranja ena najlažjih za pisanje, je zelo pomembna, saj praviloma preprost projekt zahteva le preprost zapis, in ne ogromen algoritem, ki ga sami ne morete napisati. Timsort tudi ni najbolj zapleten algoritem, vendar mu naslov najpreprostejšega ne sija.

Implementacija algoritma

No, dobili smo "slastno". Oglejmo si, kako je ta algoritem implementiran. Kot smo že omenili, ni preveč zapleteno izvajati, še bolj preprosto. Vendar pa še vedno popolnoma analiziramo vsako dejanje naše kode, da boste razumeli, kako hitro deluje sortiranje.

Naša metoda se imenuje quickSort. Izvaja glavni algoritem, v katerem prenesemo matriko, njen prvi in ​​zadnji element. Zapomnimo si spremenljivke i in k prvi in ​​zadnji element razvrščenega segmenta, da ne spremenimo teh spremenljivk, kot jih potrebujemo. Potem preverimo razdaljo med prvim in zadnjim preverjenim: je večja ali enaka eni? Če ne, potem smo prišli v središče in se moramo izločiti iz tega segmenta, in če je tako, nadaljujemo razvrščanje.

Nato vzamemo prvi element v segmentu, ki je razvrščen za podporni element. Naslednji cikel naredimo, dokler ne pridemo do centra. V njej naredimo še dva cikla: prvi je za levi del, drugi pa za desno. Izvajamo jih tako dolgo, dokler obstajajo elementi, ki ustrezajo pogoju, ali dokler ne dosežemo podpornega elementa. Potem, če je minimalni element še vedno na desni in maksimum na levi, jih zamenjajte. Ko se cikel konča, spremenite prvi element in sklic, če je referenca manjša. Potem rekurzivno naredimo naš algoritem za desni in levi del matrike in tako nadaljujemo, dokler ne dosežemo segmenta z 1 elementom v dolžini. Nato se bodo vrnili vsi naši rekurzivni algoritmi in popolnoma bomo izstopili iz te vrste. Tudi na dnu je metoda swap - standardna metoda pri razvrščanju niza nadomestkov. Da ne bi večkrat pisali zamenjave elementov, smo enkrat napisali in spremenili elemente v tem nizu.

Skratka, lahko rečemo, da je hitrostno razvrščanje glede na razmerje med kakovostjo in kompleksnostjo vodilno mesto med vsemi algoritmi, zato morate vsekakor zapisati metodo in jo uporabiti, če je potrebno v vaših projektih.