Introduksjon til Quick Sort i Java
Følgende artikkel Quick Sort in Java gir en oversikt for hurtigsorteringsalgoritmen i java. Hurtigsorteringsalgoritmen er en av sorteringsalgoritmene som er effektive og lik den for sammenslåingssorteringsalgoritmen. Dette er en av de ofte brukte algoritmene for sanntids sorteringsformål. Tidskompleksiteten i verste fall av denne algoritmen er O (n 2), tidskompleksiteten i gjennomsnittet er O (n log n) og den beste sakskompleksiteten er O (n log n).
Plasskompleksiteten hvis O (n log n) hvor er n er størrelsen på inngangen. Prosessen med sortering innebærer partisjonering av input, rekursive iterasjoner og markering av et sentralt element for hver rekursjon. Typen av sortering i denne algoritmen innebærer en sammenligning av tilstøtende elementer på en iterativ måte.
Hvordan Quick Sort fungerer i Java?
Quick Sort-algoritmen kan implementeres i Java ved å danne en pseudokode med en sekvens av trinn designet og fulgt på en effektiv måte.
- Hovedprinsippet for hurtigsorteringsalgoritmen som den fungerer er basert på skillet og erobre-tilnærmingen og er også en effektiv sorteringsalgoritme.
- Inngangsmatrisen er delt inn i delmatriser og inndelingen er basert på svingelement som er et sentralt element. Undergruppene på hver side av dreieelementet er hovedområdene der sorteringen faktisk skjer.
- Det sentrale dreieelementet er basen for å dele oppstillingen i to skillevegger der den venstre halvdelen av matriselementene er mindre enn svingelementet, og den høyre halvdelen av matriselementene er større enn svingelementet.
- Før du vurderer pivotelementet, kan det være hvem som helst fra elementene i en matrise. Dette blir normalt sett på som den ene eller den første eller den siste for å forstå. Pivotelementet kan være et tilfeldig element fra hvilket som helst av matriseelementene.
- I vårt eksempel blir det siste elementet i en matrise betraktet som et pivottelement, der partisjoneringen av delarrayer starter fra høyre ende av arrayen.
- Til slutt vil pivotelementet være i sin faktiske sorterte posisjon etter fullføringen av sorteringsprosessen der hovedprosessen med sortering ligger i partisjonslogikken til sorteringsalgoritmen.
- Effektiviteten til algoritmen avhenger av størrelsen på undergruppene og hvordan de er balanserte. Jo mer undergruppene er ubalanserte, jo mer vil tidskompleksiteten føre til worst-case kompleksitet.
- Valg av pivotelementer på en tilfeldig måte resulterer i den beste tidskompleksiteten i mange tilfeller i stedet for å velge en bestemt start-, slutt- eller midtindeks som pivotelementene.
Eksempler på implementering av hurtigsortering i Java
QuickSort-algoritmen er implementert ved å bruke Java-programmeringsspråk som nedenfor, og utgangskoden har blitt vist under koden.
- Koden tar inngangen til å begynne med metoden quickSortAlgo () med matrisen, den første indeksen og den endelige indeksen, dvs. lengden på matrisen som argumenter.
- Etter å ha ringt metoden quickSortAlgo (), sjekker den om den innledende indeksen er mindre enn den endelige indeksen, og kaller deretter metoden arrayPartition () for å få pivotelementverdi.
- Partisjonselementet inneholder logikken i å arrangere de mindre og større elementene rundt pivotelementet basert på elementverdiene.
- Etter å ha fått pivotelementindeksen etter utførelse av partisjonsmetoden, kalles quickSortAlgo () -metoden av seg selv rekursivt til alle delarrayene er partisjonert og sortert fullstendig.
- I partisjonslogikken blir det siste elementet tilordnet som svingelement og det første elementet sammenlignes med pivottelementet, dvs. det siste der elementene byttes ut fra om de er mindre eller større.
- Denne rekursjonsprosessen skjer til alle elementene i en matrise er delt opp og sortert der det endelige resultatet er en kombinert sortert matrise.
- Elementene byttes inne i for-loop-iterasjonen bare i tilfelle elementet er mindre enn eller lik svingelementet.
- Etter å ha fullført iterasjonsprosessen, byttes det siste elementet, dvs. pivotelementverdien flyttes til venstre side slik at de nye partisjonene lages og den samme prosessen gjentas i form av rekursjon som resulterer i serie sorteringsoperasjoner på forskjellige mulige partisjoner som en formasjon av undergrupper ut av de gitte arrayelementer.
- Koden nedenfor kan kjøres på hvilken som helst IDE, og utdataene kan verifiseres ved å endre rekkeverdien i hovedmenyen () Hovedmetoden brukes bare for å få utdataene i konsollen. Som en del av Java-kodingsstandarder kan hovedmetoden fjernes nedenfor og et objekt kan opprettes og nedenfor kan metoder kalles ved å gjøre dem ikke-statiske.
Kodeimplementering av hurtigsorteringsalgoritme i Java
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Produksjon:
Konklusjon
Hurtigsorteringsalgoritmen er effektiv, men ikke mye stabil sammenlignet med andre sorteringsteknikker. Effektiviteten av raske sorteringsalgoritmer kommer ned i tilfelle av et større antall gjentatte elementer, noe som er en ulempe. Plasskompleksiteten er optimalisert i denne raske algoritmen.
Anbefalte artikler
Dette er en guide til Quick Sort i Java. Her diskuterer vi hvordan Quick Sort fungerer i Java sammen med et eksempel og implementering av kode. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -
- Heap Sort In Java
- Hva er et binærtre i Java?
- Bitmanipulering i Java
- Oversikt over Merge Sort i JavaScript
- Oversikt over Rask Sortering i JavaScript
- Heap Sort in Python
- Topp 6 sorteringsalgoritme i JavaScript