Quicksort Algorithm Implementation in Java

1. Oversikt

I denne opplæringen vil vi utforske QuickSort-algoritmen i detalj, med fokus på Java-implementeringen.

Vi vil også diskutere fordeler og ulemper, og deretter analysere tidskompleksiteten.

2. QuickSort-algoritme

Quicksort er en sorteringsalgoritme som utnytter del-og-erobre-prinsippet. Det har et gjennomsnitt O (n log n) kompleksitet, og det er en av de mest brukte sorteringsalgoritmene, spesielt for store datavolumer.

Det er viktig å huske at Quicksort ikke er en stabil algoritme. En stabil sorteringsalgoritme er en algoritme der elementene med de samme verdiene vises i samme rekkefølge i den sorterte utgangen som de vises i inngangslisten.

Inngangslisten er delt inn i to underlister med et element som kalles pivot; en underliste med elementer mindre enn pivoten og en annen med elementer som er større enn pivot. Denne prosessen gjentas for hver underliste.

Til slutt smelter alle sorterte underlister sammen for å danne den endelige utdata.

2.1. Algoritmetrinn

  1. Vi velger et element fra listen, kalt pivot. Vi bruker den til å dele listen opp i to underlister.
  2. Vi ordner om alle elementene rundt pivoten - de med mindre verdi er plassert foran den, og alle elementene større enn pivoten etter den. Etter dette trinnet er svingpunktet i sin endelige posisjon. Dette er det viktige partisjonstrinnet.
  3. Vi bruker trinnene ovenfor rekursivt på begge underlister til venstre og høyre for dreietappen.

Som vi kan se, quicksort er naturlig nok en rekursiv algoritme, som hver deling og erobringstilnærming.

La oss ta et enkelt eksempel for å bedre forstå denne algoritmen.

Arr [] = {5, 9, 4, 6, 5, 3}
  1. La oss anta at vi velger 5 som ledd for enkelhet
  2. Vi setter først alle elementene mindre enn 5 i den første posisjonen til matrisen: {3, 4, 5, 6, 5, 9}
  3. Deretter gjentar vi den for venstre undergruppe {3,4}, og tar 3 som svingpunkt
  4. Det er ingen elementer mindre enn 3
  5. Vi bruker kviksort på undermatrisen til høyre for svingpunktet, dvs. {4}
  6. Denne undergruppen består av bare ett sortert element
  7. Vi fortsetter med høyre del av den opprinnelige matrisen, {6, 5, 9} til vi får den endelige bestilte matrisen

2.2. Velge Optimal Pivot

Det avgjørende poenget i QuickSort er å velge den beste pivoten. Midterelementet er selvfølgelig det beste, da det vil dele listen i to like store underlister.

Men å finne midtelementet fra en uordnet liste er vanskelig og tidkrevende, det er derfor vi tar det første elementet, det siste elementet, medianen eller et hvilket som helst annet tilfeldig element som dreiepunkt.

3. Implementering i Java

Den første metoden er quickSort () som tar som parametere matrisen som skal sorteres, den første og den siste indeksen. Først sjekker vi indeksene og fortsetter bare hvis det fortsatt er elementer som skal sorteres.

Vi får indeksen over den sorterte pivoten og bruker den til å rekursivt ringe skillevegg() metoden med samme parametere som quickSort () metode, men med forskjellige indekser:

public void quickSort (int arr [], int begin, int end) {if (begin <end) {int partitionIndex = partition (arr, begin, end); quickSort (arr, start, partitionIndex-1); quickSort (arr, partitionIndex + 1, slutt); }}

La oss fortsette med skillevegg() metode. For enkelhets skyld tar denne funksjonen det siste elementet som ledd. Kontroller deretter hvert element og bytter det før pivoten hvis verdien er mindre.

Ved slutten av partisjonen er alle elementene mindre enn svingpunktet til venstre for den, og alle elementene større enn svingpunktet er til høyre for den. Pivoten er i sin endelige sorterte posisjon, og funksjonen returnerer denne posisjonen:

privat int-partisjon (int arr [], int start, int end) {int pivot = arr [end]; int i = (begynn-1); for (int j = start; 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 [slutt]; arr [end] = swapTemp; retur i + 1; }

4. Algoritmeanalyse

4.1. Tidskompleksitet

I beste fall vil algoritmen dele listen i to underlister av samme størrelse. Så, den første iterasjonen av det fulle nstørrelse størrelse behov På). Sorter de resterende to underlistene med n / 2 elementer tar 2 * O (n / 2) Hver. Som et resultat har QuickSort-algoritmen kompleksiteten til O (n log n).

I verste fall vil algoritmen bare velge ett element i hver iterasjon, så O (n) + O (n-1) +… + O (1), som er lik O (n2).

I snitt har QuickSort O (n log n) kompleksitet, noe som gjør den egnet for store datamengder.

4.2. QuickSort vs MergeSort

La oss diskutere i hvilke tilfeller vi skal velge QuickSort fremfor MergeSort.

Selv om både Quicksort og Mergesort har en gjennomsnittlig tidskompleksitet på O (n log n), Quicksort er den foretrukne algoritmen, da den har en O (logg (n)) romkompleksitet. Fusjon, derimot, krever På) ekstra lagring, noe som gjør det ganske dyrt for matriser.

Quicksort krever tilgang til forskjellige indekser for sin virksomhet, men denne tilgangen er ikke direkte mulig i koblede lister, ettersom det ikke er noen kontinuerlige blokker. derfor for å få tilgang til et element må vi iterere gjennom hver node fra begynnelsen av den koblede listen. Mergesort er også implementert uten ekstra plass til LinkedLists.

I slike tilfeller foretrekkes generelt økninger i overhead for Quicksort og Mergesort.

5. Konklusjon

Quicksort er en elegant sorteringsalgoritme som er veldig nyttig i de fleste tilfeller.

Det er vanligvis en "på plass" -algoritme, med gjennomsnittlig tidskompleksitet på O (n log n).

Et annet interessant poeng å nevne er at Java’s Arrays.sort () metoden bruker Quicksort for å sortere matriser av primitiver. Implementeringen bruker to pivoter og fungerer mye bedre enn den enkle løsningen vår. Derfor er det vanligvis bedre å bruke biblioteksmetoder for produksjonskode.

Som alltid kan koden for implementering av denne algoritmen finnes på GitHub-depotet vårt.