QuickSort is een verdeel & heers-algoritme. In het algoritmeontwerpparadigma van Divide & Conquer verdelen we de problemen recursief in subproblemen en lossen vervolgens de subproblemen op en combineren uiteindelijk de oplossingen om het eindresultaat te vinden. In dit artikel zullen we ons concentreren op QuickSort In
De volgende tips komen in dit artikel aan bod:
aws-startinstantie vanaf momentopname
Laten we beginnen!
Een ding om in gedachten te houden bij het opdelen van de problemen in deelproblemen is dat de structuur van deelproblemen niet verandert vanaf het oorspronkelijke probleem.
Het Divide & Conquer-algoritme bestaat uit 3 stappen:
- Verdelen: het probleem opdelen in subproblemen
- Veroveren: de subproblemen recursief oplossen
- Combineren: het combineren van de oplossingen om het uiteindelijke resultaat te krijgen
Er zijn verschillende algoritmen gebaseerd op het verdeel & heers-paradigma. Snel sorteren en sorteren samenvoegen zijn er onder.
Hoewel de worst-case tijdcomplexiteit van QuickSort O (n2) is, wat meer is dan veel andere sorteeralgoritmen zoals Merge Sort en Heap Sort, is QuickSort in de praktijk sneller, omdat de binnenlus efficiënt kan worden geïmplementeerd op de meeste architecturen, en in de meeste real-world data.
Laten we het hebben over de implementatie van het Quick sort-algoritme. Quicksort-algoritmen nemen een pivot-element en verdelen de array rond het pivot-element. Er zijn een aantal variaties op Quicksot die afhangen van hoe u het pivot-element kiest. Er zijn meerdere manieren om het draaipunt te kiezen:
- Het eerste element kiezen
- Kies het laatste element
- Een willekeurig element kiezen
- Mediaanelement kiezen
Het volgende belangrijke ding om te begrijpen is, de partition () functie in het Quick sort-algoritme. Scheidingsfunctie om een draai-element te nemen, plaatst het in de juiste positie, verplaatst alle elementen kleiner dan het draai-element naar links en alle elementen groter naar rechts. Quicksort heeft hier lineaire tijd voor nodig.
Vervolgens wordt de array verdeeld in twee delen van het pivot-element (d.w.z. elementen kleiner dan pivot en elementen groter dan pivot) en beide arrays worden recursief gesorteerd met behulp van het Quicksort-algoritme.
Nu we de werking van het QuickSort-algoritme begrijpen. Laten we eens kijken hoe we het Quicksort-algoritme in Java kunnen implementeren.
Snel sorteren Functie:
/ * Quicksort-functie vereist dat de array wordt gesorteerd met de laagste en hoogste index * /
void sort (int arr [], int lowIndex, int highIndex) {// Tot lowIndex = highIndex if (lowIndexLaten we nu eens kijken naar de partitioneringscode om te begrijpen hoe het werkt.
Partitie Code
In de partitioneringscode kiezen we het laatste element als het pivot-element. We doorlopen de volledige array (dat wil zeggen met behulp van variabele j in ons geval). We houden het laatste kleinste element in de array bij (dat wil zeggen met behulp van variabele i in ons geval). Als we een element vinden dat kleiner is dan het draaipunt, verplaatsen we swap current element a [j] met arr [i], anders blijven we doorlopen.
int partitie (int arr [], int lowIndex, int highIndex) {// Het laatste element als pivot maken int pivot = arr [highIndex] // i gebruiken om kleinere elementen van pivot int i = (lowIndex-1) bij te houden voor (int j = lowIndex jNu je de Quicksort & partition-functie hebt begrepen, kunnen we snel de volledige code bekijken
Snel sorteren Java Code
class QuickSort {// Partitie Methode int partitie (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) voor (int j = lowIndex j// Sorteermethode
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Methode om array af te drukken
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Hoofdmethode
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('gesorteerde array') printArray (arr)}} Uitgang:
Nu, na het uitvoeren van het bovenstaande Java-programma, zou u hebben begrepen hoe QuickSort werkt en hoe u het in Java kunt implementeren.Hiermee zijn we aan het einde gekomen van dit artikel over ‘Quicksort in Java’. Als u meer wilt weten,bekijk de door Edureka, een vertrouwd online leerbedrijf. Edureka's Java J2EE- en SOA-trainings- en certificeringscursus is ontworpen om u te trainen in zowel kern- als geavanceerde Java-concepten, samen met verschillende Java-frameworks zoals Hibernate & Spring.
Heeft u een vraag voor ons? Vermeld het in het opmerkingengedeelte van deze blog en we nemen zo snel mogelijk contact met je op.