Brzo sortiranje je jedna od najboljih metoda sortiranja nizova.

Ako programirate i vaš kod nadilazi pisanje kalkulatora, često ćete se susresti ili biti suočeni s potrebom sortiranja određenog niza podataka. Postoji mnogo načina za sortiranje. U ovom članku ćemo analizirati glavne od njih i usredotočiti se na brzo sortiranje.

Brzo sortiranje

Brzo sortiranje - Quick Sort ili qsort. Po imenu postaje jasno što je to i zašto. Ali ako nije jasno, onda ovo je algoritam Brzim sortiranjem niza, algoritam u prosjeku ima O (n log n) učinkovitost. Što to znači? To znači da se prosječno vrijeme rada algoritma povećava duž iste putanje kao i graf ove funkcije. Neki popularni jezici imaju ugrađene knjižnice s ovim algoritmom, što već ukazuje na to da je izuzetno učinkovit. To su jezici kao što su Java, C ++, C #.

Algoritam

Brza metoda sortiranja koristi rekurziju i strategiju "Podijeli i osvoji".

1. U nizu tražimo određeni element podrške, zbog jednostavnosti, bolje je uzeti središnji element, ali ako želite raditi na optimizaciji, morat ćete isprobati različite opcije.

2. S lijeve strane oslonca traži se element veći od referencije, s desne strane, manji element od reference, a onda ih zamijenimo. Učinite to sve dok maksimum na desnoj strani nije manji od minimuma na lijevoj strani. Tako se svi mali elementi bacaju na početak, veliki - do kraja.

3. Rekurzivno primijenite ovaj algoritam na lijevi i desni dio našeg algoritma zasebno, zatim opet i opet, sve dok ne dođete do jednog elementa ili određenog broja elemenata. Koji je to broj elemenata? Postoji još jedan način optimiziranja tog algoritma. Kada sortirani dio postane približno jednak 8 ili 16, on se može obraditi svojim uobičajenim sortiranjem, primjerice sortiranjem mjehurića. Stoga ćemo povećati učinkovitost našeg algoritma ne obrađuje male nizove što je brže moguće.

Stoga će se cijeli niz obraditi i razvrstati. Sada ćemo vizualno proučiti ovaj algoritam.

Brzo razvrstavanje

Je li brzo sortiranje najbrži algoritam za sortiranje? Definitivno ne. Sada je sve više i više sortiranja, u trenutku kada je najbrže sortiranje Timsort, radi iznimno brzo za matrice koje su izvorno sortirane drugačije. Ali ne zaboravite da je brza metoda sortiranja jedna od najlakših za pisanje, vrlo je važna, jer, u pravilu, jednostavan projekt zahtijeva samo jednostavan pravopis, a ne ogroman algoritam koji vi sami ne možete napisati. Timsort također nije najsloženiji algoritam, ali naslov najjednostavnijega za njega ne sjaji.

Implementacija algoritma

Pa, došli smo do "ukusnog". Pogledajmo sada kako je implementiran ovaj algoritam. Kao što je ranije spomenuto, nije previše komplicirano provoditi, a čak i jednostavno. Ali još uvijek u potpunosti analiziramo svaku akciju našeg koda, tako da razumijete kako brzo radi sortiranje.

Naša metoda se naziva quickSort. Pokreće glavni algoritam u kojem prenosimo polje, njegove prve i zadnje elemente. Zapamtimo u varijablama i i k prvi i posljednji element sortiranog segmenta kako ne bismo mijenjali te varijable, koliko ih trebamo. Zatim provjeravamo udaljenost između prve i zadnje provjere: je li ona veća ili jednaka jednom? Ako ne, onda smo došli u središte i moramo izaći iz razvrstavanja ovog segmenta, i ako je tako, nastavljamo sortiranje.

Zatim uzimamo prvi element u segmentu koji je sortiran za potporni element. Sljedeći ciklus obavljamo dok ne dođemo do centra. U njemu radimo još dva ciklusa: prvi je za lijevi dio, a drugi za desni. Izvodimo ih sve dok postoje elementi koji odgovaraju stanju ili dok ne dođemo do elementa podrške. Zatim, ako je minimalni element još uvijek desno, a maksimum na lijevoj strani, zamijenite ih. Kada se ciklus završi, promijenite prvi element i referencu, ako je referenca manja. Zatim rekurzivno napravimo naš algoritam za desni i lijevi dio polja, i tako nastavimo sve dok ne dođemo do segmenta duljine 1 elementa. Tada će se svi naši rekurzivni algoritmi vratiti, a mi ćemo potpuno napustiti sortiranje. Također na dnu je swap metoda - prilično standardna metoda pri sortiranju niza zamjena. Kako ne bismo više puta pisali zamjenu elemenata, pišemo jednom i mijenjamo elemente u tom nizu.

U zaključku, možemo reći da je u smislu omjera kvalitete i složenosti, brzo sortiranje na vodećem mjestu među svim algoritmima, tako da svakako treba zapisati metodu i koristiti je ako je potrebno u vašim projektima.