Menu

QuickSort in Java - Algoritme, illustratie en implementatie

  • Hoofd
  • Andere
  • QuickSort in Java - Algoritme, illustratie en implementatie

quicksort java algorithm

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Deze tutorial legt het Quicksort-algoritme in Java uit, de illustraties, QuickSort-implementatie in Java met behulp van codevoorbeelden:

Quicksort-sorteertechniek wordt veel gebruikt in softwaretoepassingen. Quicksort gebruikt een verdeel-en-heersstrategie zoals samenvoegen en sorteren.

In het quicksort-algoritme wordt eerst een speciaal element met de naam “pivot” geselecteerd en wordt de betreffende array of lijst opgedeeld in twee subsets. De gepartitioneerde subsets kunnen al dan niet even groot zijn.

​ Lees de Easy Java Training Series door.

QuickSort-techniek in Java

De schotten zijn zodanig dat alle elementen kleiner dan het scharnierelement zich links van het draaipunt bevinden en de elementen groter dan het draaipunt rechts van het draaipunt. De Quicksort-routine sorteert de twee sublijsten recursief. Quicksort werkt efficiënt en ook sneller, zelfs voor grotere arrays of lijsten.

Wat je leert:

Quicksort Partition Java

Partitioneren is het belangrijkste proces van de Quicksort-techniek. Dus wat is partitioneren?

Gegeven een array A, kiezen we een waarde x genaamd pivot, zodat alle elementen kleiner dan x vóór x staan ​​en alle elementen groter dan x na x.

Een draaipuntwaarde kan een van de volgende zijn:

  • Het eerste element in de array
  • Het laatste element in de array
  • Het middenelement in de array
  • Elk willekeurig element in de array

Deze spilwaarde wordt vervolgens op de juiste positie in de array geplaatst door de array te partitioneren. De output van het 'partitionerings'-proces is dus de draaipuntwaarde op de juiste positie en de elementen draaien minder dan links en elementen groter dan een draaipunt rechts.

Beschouw het volgende diagram waarin het partitioneringsproces wordt uitgelegd.

nep e-mailadres dat ik kan gebruiken

partitioneringsproces

Het bovenstaande diagram toont het proces van het partitioneren van de array door herhaaldelijk het laatste element in de array als draaipunt te selecteren. Merk op dat we op elk niveau de array in twee sub-arrays verdelen door het draaipunt op de juiste positie te plaatsen.

Vervolgens vermelden we het algoritme en de pseudo-code voor de quicksort-techniek die ook de partitieroutine omvat.

Quicksort-algoritme Java

Het algemene algoritme voor quicksort wordt hieronder gegeven.

​

Hieronder is de pseudo-code voor de quicksort-techniek weergegeven.

Pseudocode voor snel sorteren

Hieronder volgt de pseudo-code voor een snelle sorteertechniek. Merk op dat we de pseudo-code voor quicksort en partitioneringsroutine hebben verstrekt.

​

Illustratie

Laten we eens kijken naar de illustratie van het quicksort-algoritme. Neem de volgende array als voorbeeld. Hier hebben we het laatste element als draaipunt geselecteerd.

Zoals getoond, is het eerste element laag gelabeld en het laatste element hoog.

Illustratie van het Quicksort-algoritme

Zoals duidelijk is in de bovenstaande illustratie, zijn er twee wijzers, hoog en laag, die respectievelijk naar het laatste en eerste element van de array verwijzen. Beide aanwijzingen worden verplaatst naarmate de quicksort vordert.

Wanneer het element dat door de lage wijzer wordt aangeduid groter wordt dan het draai-element en het element dat wordt aangegeven door de hoge wijzer kleiner is dan het draai-element, wisselen we de elementen die worden aangeduid door de lage en hoge wijzer, en elke wijzer gaat 1 positie vooruit.

De bovenstaande stappen worden uitgevoerd totdat beide wijzers elkaar kruisen in de array. Zodra ze elkaar kruisen, krijgt het scharnierelement zijn juiste positie in de reeks. Op dit punt is de array gepartitioneerd en nu kunnen we elke sub-array onafhankelijk sorteren door recursief een snel sorteeralgoritme toe te passen op elk van de sub-array.

hoe jnlp-bestand in Windows 10 uit te voeren

Quicksort-implementatie in Java

De QuickSort-techniek kan in Java worden geïmplementeerd met behulp van recursie of iteratie. In deze sectie zullen we beide technieken zien.

Recursieve Quicksort

We weten dat de hierboven geïllustreerde basistechniek van quicksort recursie gebruikt voor het sorteren van de array. In de recursieve quicksort na het partitioneren van de array, wordt de quicksort-routine recursief aangeroepen om de sub-arrays te sorteren.

De onderstaande implementatie demonstreert de quicksort-techniek met behulp van recursie.

​

Uitgang:

Oorspronkelijke matrix: (4, -1, 6, 8, 0, 5, -3)
Gesorteerde matrix: (-3, -1, 0, 4, 5, 6, 8)

Recursieve quicksort - uitvoer

Iteratieve Quicksort

In iteratieve quicksort gebruiken we de hulpstack om tussenliggende parameters te plaatsen in plaats van recursie- en sorteerpartities te gebruiken.

Het volgende Java-programma implementeert een iteratieve quicksort.

wat is een swf-bestand?
​

Uitgang:

Oorspronkelijke matrix: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Gesorteerde matrix: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Iteratieve quicksort - output

Veel Gestelde Vragen

Q # 1) Hoe werkt een Quicksort?

Antwoord: Quicksort hanteert een verdeel- en veroveringsstrategie. Quicksort verdeelt eerst een array rond een geselecteerd pivot-element en genereert sub-arrays die recursief worden gesorteerd.

Vraag 2) Wat is de tijdcomplexiteit van Quicksort?

Antwoord: De tijdcomplexiteit van quicksort gemiddeld is O (nlogn). In het ergste geval is het O (n ^ 2) hetzelfde als de selectiesortering.

V # 3) Waar wordt Quicksort gebruikt?

Antwoord: Quicksort wordt vooral gebruikt in recursieve applicaties. Quicksort is het onderdeel van C-library. Ook implementeren bijna de programmeertalen die ingebouwde sortering gebruiken quicksort.

Q # 4) Wat is het voordeel van Quicksort?

Antwoord:

  • Quicksort is een efficiënt algoritme en kan zelfs een enorme lijst met elementen gemakkelijk sorteren.
  • Het is op zijn plaats gesorteerd en heeft daarom geen extra ruimte of geheugen nodig.
  • Het wordt veel gebruikt en biedt een efficiënte manier om gegevenssets van elke lengte te sorteren.

V # 5) Waarom is Quicksort beter dan samenvoegen?

Antwoord: De belangrijkste reden waarom de quicksort beter is dan de merge-sortering, is dat quicksort een in-place sorteermethode is en geen extra geheugenruimte vereist. Samenvoegen sorteren vereist extra geheugen voor tussentijdse sortering.

Gevolgtrekking

Quicksort wordt beschouwd als het beste sorteeralgoritme, voornamelijk vanwege zijn efficiëntie om zelfs een enorme dataset in O (nlogn) -tijd te sorteren.

Quicksort is ook een in-place sortering en vereist geen extra geheugenruimte. In deze tutorial hebben we de recursieve en iteratieve implementatie van quicksort gezien.

In onze aanstaande tutorial gaan we verder met sorteermethoden in Java.

​ Bekijk hier de Java-beginnershandleiding.

Aanbevolen literatuur

^