Introduktion til hurtig sortering i Java
Den følgende artikel Hurtig sortering i Java giver en oversigt over hurtigsorteringsalgoritmen i java. Den hurtige sorteringsalgoritme er en af sorteringsalgoritmerne, som er effektiv og ligner den for flettsorteringsalgoritmen. Dette er en af de almindeligt anvendte algoritmer til realtids sorteringsformål. Tidskompleksiteten i værste tilfælde af denne algoritme er O (n 2), den gennemsnitlige tidskompleksitet er O (n log n), og den bedste case-kompleksitet er O (n log n).
Rumkompleksiteten, hvis O (n log n) hvor er n, er størrelsen på input. Processen med sortering involverer partitionering af input, rekursive iterationer og markering af et centralt element for hver rekursion. Sorteringstypen i denne algoritme involverer en sammenligning af tilstødende elementer på en iterativ måde.
Hvordan Quick Sort fungerer i Java?
Quick Sort-algoritme kan implementeres i Java ved at danne en pseudokode med en række trin designet og fulgt på en effektiv måde.
- Hovedprincippet for den hurtige sorteringsalgoritme, som den fungerer, er baseret på skillet og erobre tilgangen og er også en effektiv sorteringsalgoritme.
- Indgangsarrayet er opdelt i underarrays, og opdelingen er baseret på et svingelement, som er et centralt element. Undergrupperne på hver side af drejeelementet er de vigtigste områder, hvor sorteringen faktisk finder sted.
- Det centrale pivotelement er basen til at opdele arrayet i to partitioner, hvor den venstre halvdel af arrayelementerne er mindre end pivotelementet, og den højre halvdel af arrayelementerne er større end pivotelementet.
- Inden man tænker pivotelementet, kan det være hvem som helst fra elementerne i en matrix. Dette betragtes normalt som midterste eller første eller sidste for at lette forståelsen. Pivotelementet kan være et tilfældigt element fra et hvilket som helst af arrayelementerne.
- I vores eksempel betragtes det sidste element i en matrix som et pivotelement, hvor opdelingen af undergrupper starter fra højre ende af matrixen.
- Endelig vil drejeelementet være i sin faktiske sorterede position efter afslutningen af sorteringsprocessen, hvor hovedprocessen med sortering ligger i partitionslogikken i sorteringsalgoritmen.
- Effektiviteten af algoritmen afhænger af størrelsen på undergrupperne, og hvordan de er afbalancerede. Jo mere undergrupperne er ubalanceret, desto mere vil tidskompleksiteten føre til worst-case kompleksitet.
- Valg af pivotelementer på en tilfældig måde resulterer i den bedste tidskompleksitet i mange tilfælde i stedet for at vælge et bestemt start-, slut- eller midtindeks som pivotelementerne.
Eksempler på implementering af hurtig sortering i Java
QuickSort-algoritmen er implementeret ved hjælp af Java-programmeringssprog som nedenfor, og outputkoden er vist under koden.
- Koden indtager oprindeligt input ved hjælp af metoden quickSortAlgo () med array, startindeks og slutindeks, dvs. længden af arrayet som argumenter.
- Efter at have ringet til metoden quickSortAlgo (), kontrollerer den, om det indledende indeks er mindre end det endelige indeks, og kalder derefter arrayPartition () -metoden for at få pivotelementværdien.
- Partitionselementet indeholder logikken i at arrangere de mindre og større elementer rundt om pivotelementet baseret på elementværdierne.
- Efter at have hentet pivotelementindekset efter eksekvering af partitionsmetoden, kaldes quickSortAlgo () -metoden af sig selv rekursivt, indtil alle undergrupper er partitioneret og sorteret fuldstændigt.
- I partitionslogikken tildeles det sidste element som pivotelement, og det første element sammenlignes med pivotelementet, dvs. det sidste, hvor elementerne byttes ud fra om de er mindre eller større.
- Denne rekursionsproces sker, indtil alle elementerne i en matrix er delt og sorteret, hvor det endelige resultat er et kombineret sorteret array.
- Elementerne udskiftes inden i for-loop-iterationen kun i tilfælde af, at elementet er mindre end eller lig med drejeelementet.
- Efter at iterationsprocessen er afsluttet, udskiftes det sidste element, dvs. pivotelementværdien flyttes til venstre side, så de nye partitioner oprettes, og den samme proces gentages i form af rekursion, hvilket resulterer i en række sorteringsoperationer på forskellige mulige partitioner som en dannelse af undergrupper ud af de givne matrixelementer.
- Nedenstående kode kan køres på enhver IDE, og output kan verificeres ved at ændre array-værdien i hovedmenuen () Hovedmetoden bruges kun til at få output i konsollen. Som en del af Java-kodningsstandarder kan hovedmetoden fjernes nedenfor, og et objekt kan oprettes, og nedenfor kan metoder kaldes ved at gøre dem ikke-statiske.
Kodeimplementering af hurtig sorteringsalgoritme 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);
)
)
)
Produktion:
Konklusion
Den hurtige sorteringsalgoritme er effektiv, men ikke meget stabil sammenlignet med andre sorteringsteknikker. Effektiviteten af hurtige sorteringsalgoritmer kommer ned i tilfælde af et større antal gentagne elementer, hvilket er en ulempe. Rumkompleksiteten optimeres i denne hurtige sorteringsalgoritme.
Anbefalede artikler
Dette er en guide til hurtig sortering i Java. Her diskuterer vi, hvordan Quick Sort fungerer i Java sammen med et eksempel og implementering af kode. Du kan også gennemgå vores andre foreslåede artikler for at lære mere -
- Heap sortering i Java
- Hvad er et binært træ i Java?
- Bitmanipulation i Java
- Oversigt over fletningssortering i JavaScript
- Oversigt over hurtig sortering i JavaScript
- Heap Sort i Python
- Top 6 sorteringsalgoritme i JavaScript