Introductie tot Quick Sort in Java
Het volgende artikel Snel sorteren in Java biedt een overzicht van het algoritme voor snel sorteren in Java. Het Quick Sort-algoritme is een van de sorteeralgoritmen die efficiënt is en vergelijkbaar met die van het merge-sorteeralgoritme. Dit is een van de meest gebruikte algoritmen voor realtime sorteerdoeleinden. De tijdcomplexiteit van het slechtste geval van dit algoritme is O (n 2), de tijdcomplexiteit van het gemiddelde geval is O (n log n) en de tijdcomplexiteit van het beste geval is O (n log n).
De ruimtecomplexiteit als O (n log n) waar n is, is de grootte van de invoer. Het sorteerproces omvat het partitioneren van invoer, recursieve iteraties en het markeren van een cruciaal element voor elke recursie. Het type sortering in dit algoritme omvat een vergelijking van aangrenzende elementen op een iteratieve manier.
Hoe werkt Quick Sort in Java?
Quick Sort-algoritme kan in Java worden geïmplementeerd door een pseudocode te vormen met een reeks stappen die op een efficiënte manier zijn ontworpen en gevolgd.
- Het belangrijkste principe van het snelle sorteeralgoritme dat het werkt, is gebaseerd op de verdeel en heers aanpak en is ook een efficiënt sorteeralgoritme.
- De invoerarray is verdeeld in subarrays en de verdeling is gebaseerd op een draai-element dat een centraal element is. De subarrays aan weerszijden van het scharnierelement zijn de belangrijkste gebieden waar het sorteren daadwerkelijk plaatsvindt.
- Het centrale draai-element is de basis om de reeks te verdelen in twee partities waar de linkerhelft van reekselementen kleiner is dan het draai-element en de rechterhelft van reekselementen groter is dan het draai-element.
- Voordat het draaipunt wordt overwogen, kan dit iedereen uit de elementen van een array zijn. Dit wordt normaal beschouwd als middelste of eerste of laatste voor het gemak van begrip. Het draai-element kan willekeurig zijn van elk van de array-elementen.
- In ons voorbeeld wordt het laatste element van een array beschouwd als een pivot-element, waarbij het partitioneren van subarrays begint vanaf het rechteruiteinde van de array.
- Tenslotte zal het draaielement zich in zijn werkelijke gesorteerde positie bevinden na de voltooiing van het sorteerproces waar het hoofdproces van sorteren in de partitielogica van het sorteeralgoritme ligt.
- De efficiëntie van het algoritme is afhankelijk van de grootte van de subarrays en hoe deze in evenwicht zijn. Hoe meer de subarrays onevenwichtig zijn, des te meer zal de tijdcomplexiteit leiden tot de worst-case complexiteit.
- De selectie van spilelementen op een willekeurige manier resulteert in veel gevallen in de beste tijdcomplexiteit in plaats van een bepaalde begin-, eind- of middenindexen te kiezen als de spilelementen.
Voorbeelden om Quick Sort in Java te implementeren
Het QuickSort-algoritme is geïmplementeerd met behulp van de Java-programmeertaal zoals hieronder en de uitvoercode is onder de code weergegeven.
- De code neemt aanvankelijk de invoer met behulp van de methode quickSortAlgo () met de array, de initiële index en de laatste index, dwz de lengte van de array als argumenten.
- Nadat de methode quickSortAlgo () is aangeroepen, wordt gecontroleerd of de initiële index kleiner is dan de uiteindelijke index en wordt vervolgens de methode arrayPartition () aangeroepen om de waarde van het pivot-element te verkrijgen.
- Het partitie-element bevat de logica van het rangschikken van de kleinere en grotere elementen rond het pivot-element op basis van de elementwaarden.
- Nadat de spilelementindex is opgehaald na de uitvoering van de partitiemethode, wordt de methode quickSortAlgo () recursief aangeroepen totdat alle subarrays zijn gepartitioneerd en volledig zijn gesorteerd.
- In de partitielogica wordt het laatste element toegewezen als pivot-element en wordt het eerste element vergeleken met het pivot-element, dwz het laatste element waarbij de elementen worden verwisseld op basis van het feit of ze kleiner of groter zijn.
- Dit recursieproces vindt plaats totdat alle elementen van een array zijn gepartitioneerd en gesorteerd, waarbij het eindresultaat een gecombineerde gesorteerde array is.
- De elementen worden alleen binnen de for-lus iteratie verwisseld in het geval dat het element kleiner is dan of gelijk is aan het draai-element.
- Nadat het iteratieproces is voltooid, wordt het laatste element verwisseld, dat wil zeggen dat de waarde van het draaipunt naar de linkerkant wordt verplaatst, zodat de nieuwe partities worden gemaakt en hetzelfde proces wordt herhaald in de vorm van recursie, wat resulteert in reeksen sorteerbewerkingen op verschillende mogelijke partities als een formatie van subarrays uit de gegeven matrixelementen.
- De onderstaande code kan op elke IDE worden uitgevoerd en de uitvoer kan worden geverifieerd door de matrixwaarde in de main () te wijzigen. De hoofdmethode wordt alleen gebruikt om de output in de console te krijgen. Als onderdeel van de Java-coderingsstandaarden kan de hoofdmethode hieronder worden verwijderd en kan een object worden gemaakt en kunnen onderstaande methoden worden aangeroepen door ze niet-statisch te maken.
Code-implementatie van Quick Sort Algorithm in 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);
)
)
)
Output:
Conclusie
Het Quick Sort-algoritme is efficiënt maar niet erg stabiel in vergelijking met andere sorteertechnieken. De efficiëntie van snelle sorteeralgoritmen komt naar beneden in het geval van een groter aantal herhaalde elementen, wat een nadeel is. De ruimtecomplexiteit is geoptimaliseerd in dit snelle sorteeralgoritme.
Aanbevolen artikelen
Dit is een handleiding voor Snel sorteren op Java. Hier bespreken we hoe Quick Sort in Java werkt, samen met een voorbeeld en implementatie van code. U kunt ook onze andere voorgestelde artikelen doornemen voor meer informatie -
- Heap Sort In Java
- Wat is een binaire boom in Java?
- Bitmanipulatie in Java
- Overzicht van samenvoegen Sorteren in JavaScript
- Overzicht van snel sorteren in JavaScript
- Heap Sort in Python
- Top 6 sorteeralgoritme in JavaScript