streamalism.org

1. Pregled

U ovom uputstvu detaljno ćemo istražiti algoritam QuickSort, usredotočujući se na njegovu implementaciju Jave.

Također ćemo razgovarati o njegovim prednostima i nedostacima, a zatim ćemo analizirati njegovu vremensku složenost.

2. QuickSort algoritam

Quicksort je algoritam sortiranja koji koristi princip podijeli i osvoji. Ima prosjek O (n zapisnik n) složenosti i jedan je od najčešće korištenih algoritama za sortiranje, posebno za velike količine podataka.

Važno je zapamtiti da Quicksort nije stabilan algoritam. Stabilni algoritam sortiranja je algoritam u kojem se elementi s istim vrijednostima pojavljuju istim redoslijedom u sortiranom izlazu kao što se pojavljuju na popisu unosa.

Popis unosa podijeljen je na dva podpopisa elementom koji se naziva pivot; jedan podspis s elementima manjim od osovine i drugi s elementima većim od osovine. Ovaj se postupak ponavlja za svaki pod-popis.

Konačno, svi razvrstani pod-popisi se stapaju i čine konačni rezultat.

2.1. Koraci algoritma

1. S popisa odabiremo element koji se naziva pivot. Pomoću njega podijelit ćemo popis na dva pod-popisa.
2. Preuređujemo sve elemente oko pivota - oni s manjom vrijednošću postavljaju se ispred njega, a svi elementi veći od pivota nakon njega. Nakon ovog koraka pivot je u konačnom položaju. Ovo je važan korak podjele.
3. Gornje korake primjenjujemo rekurzivno na oba pod-popisa s lijeve i desne strane osovine.

Kao što vidimo, quicksort je prirodno rekurzivni algoritam, kao i svaki pristup podijeli i osvoji.

Uzmimo jednostavan primjer kako bismo bolje razumjeli ovaj algoritam.

Arr [] = {5, 9, 4, 6, 5, 3}

1. Pretpostavimo da za jednostavnost odaberemo 5 kao stožer
2. Prvo ćemo staviti sve elemente manje od 5 na prvo mjesto niza: {3, 4, 5, 6, 5, 9}
3. Zatim ćemo ga ponoviti za lijevi podskup {3,4}, uzimajući 3 kao stožer
4. Nema elemenata manjih od 3
5. Primjenjujemo brzi sortiranje na podniz u desnom dijelu osovine, tj. {4}
6. Ovaj se podskup sastoji od samo jednog razvrstanog elementa
7. Nastavljamo s desnim dijelom izvornog niza, {6, 5, 9} dok ne dobijemo konačni poredani niz

2.2. Odabir optimalnog pivota

Ključna je točka QuickSorta odabrati najbolji oslonac. Srednji je element, naravno, najbolji, jer bi podijelio popis na dva jednaka pod-popisa.

No pronalazak srednjeg elementa s neuređenog popisa težak je i dugotrajan, zato kao stožer uzimamo prvi element, posljednji element, medijan ili bilo koji drugi slučajni element.

3. Implementacija u Javi

Prva metoda je quickSort () koji uzima kao parametre niz koji se sortira, prvi i posljednji indeks. Prvo provjeravamo indekse i nastavljamo samo ako još ima elemenata za razvrstavanje.

Dobivamo indeks razvrstanog pivota i koristimo ga za rekurzivni poziv particija () metoda s istim parametrima kao i quickSort () metoda, ali s različitim indeksima:

javna void quickSort (int arr [], int početak, int kraj) {if (početak <kraj) {int partitionIndex = particija (arr, početak, kraj); quickSort (arr, begin, partitionIndex-1); quickSort (arr, partitionIndex + 1, kraj); }}

Nastavimo s particija () metoda. Radi jednostavnosti, ova funkcija uzima zadnji element kao stožer. Zatim provjerava svaki element i zamjenjuje ga prije osovine ako je njegova vrijednost manja.

Na kraju particije, svi elementi manje od osovine nalaze se na lijevoj strani, a svi elementi veći od osovine nalaze se na desnoj strani. Pivot je u konačnom razvrstanom položaju i funkcija vraća ovaj položaj:

privatna int particija (int arr [], int početak, int kraj) {int pivot = arr [kraj]; int i = (početak-1); for (int j = begin; j <end; j ++) {if (arr [j] <= pivot) {i ++; int swapTemp = arr [i]; arr [i] = arr [j]; arr [j] = swapTemp; }} int swapTemp = arr [i + 1]; arr [i + 1] = arr [kraj]; arr [kraj] = swapTemp; povratak i + 1; }

4. Analiza algoritma

4.1. Složenost vremena

U najboljem slučaju, algoritam će podijeliti popis na dva podpopisa jednake veličine. Dakle, prva iteracija cjeline n-veliki popis potreba Na). Razvrstavanje preostala dva pod-popisa sa n / 2 elementi traje 2 * O (n / 2) svaki. Kao rezultat, algoritam QuickSort ima složenost O (n zapisnik n).

U najgorem slučaju, algoritam će odabrati samo jedan element u svakoj iteraciji, dakle O (n) + O (n-1) +… + O (1), što je jednako O (n2).

U prosjeku QuickSort ima O (n zapisnik n) složenost, što ga čini prikladnim za velike količine podataka.

4.2. QuickSort vs MergeSort

Razgovarajmo u kojim bismo slučajevima trebali odabrati QuickSort umjesto MergeSort.

Iako i Quicksort i Mergesort imaju prosječnu vremensku složenost od O (n zapisnik n), Quicksort je preferirani algoritam, jer ima O (log (n)) složenost prostora. Mergesort, s druge strane, zahtijeva Na) dodatna pohrana, što čini prilično skupo za nizove.

Quicksort zahtijeva pristup različitim indeksima za svoje operacije, ali taj pristup nije izravno moguć na povezanim popisima, jer nema kontinuiranih blokova; stoga da bismo pristupili elementu, moramo prelaziti kroz svaki čvor s početka povezanog popisa. Također, Mergesort je implementiran bez dodatnog prostora za LinkedLists.

U takvom slučaju općenito je poželjno povećanje režijskih troškova za Quicksort i Mergesort.

5. Zaključak

Quicksort je elegantan algoritam sortiranja koji je vrlo koristan u većini slučajeva.

To je općenito algoritam "na mjestu", s prosječnom vremenskom složenošću od O (n zapisnik n).

Još jedna zanimljiva točka koju treba spomenuti je ona Java Nizovi.sort () metoda koristi Quicksort za sortiranje nizova primitiva. Implementacija koristi dva pivota i izvodi se puno bolje od našeg jednostavnog rješenja, zato je za proizvodni kod obično bolje koristiti metode knjižnice.

Kao i uvijek, kod za implementaciju ovog algoritma možete pronaći na našem GitHub repozitorijumu.