Snel sorteren in C ++ met voorbeelden

quick sort c with examples

Quicksort in C ++ met illustratie.

Quicksort is een veelgebruikt sorteeralgoritme dat een specifiek element met de naam 'pivot' selecteert en de array of lijst verdeelt om in twee delen te worden gesorteerd op basis van dit pivot, zodat de elementen die kleiner zijn dan het pivot zich links van de lijst en de elementen bevinden groter dan het draaipunt aan de rechterkant van de lijst.

De lijst is dus opgedeeld in twee sublijsten. De sublijsten zijn mogelijk niet nodig voor dezelfde grootte. Quicksort roept zichzelf vervolgens recursief op om deze twee sublijsten te sorteren.

​ Bekijk hier de perfecte C ++ trainingsgids.

Wat je leert:

• Invoering
• Algemeen algoritme
• Pseudo-code voor Quicksort
• Illustratie
• C ++ Voorbeeld
• Java-voorbeeld
• Complexiteitsanalyse van het Quicksort-algoritme
• 3-weg Quicksort
• Gerandomiseerde Quicksort
• Quicksort versus samenvoegen sorteren
• Gevolgtrekking
• Aanbevolen literatuur

Invoering

Quicksort werkt zowel efficiënt als sneller, zelfs voor grotere arrays of lijsten.

In deze tutorial zullen we meer onderzoeken over de werking van Quicksort, samen met enkele programmeervoorbeelden van het quicksort-algoritme.

Als spilwaarde kunnen we kiezen voor de eerste, laatste of de middelste waarde of een willekeurige waarde. Het algemene idee is dat de pivotwaarde uiteindelijk op de juiste positie in de array wordt geplaatst door de andere elementen in de array naar links of rechts te verplaatsen.

Algemeen algoritme

Het algemene algoritme voor Quicksort wordt hieronder gegeven.

Laten we nu eens kijken naar de pseudocode voor Quicksort-techniek.

Pseudo-code voor Quicksort

De werking van het partitioneringsalgoritme wordt hieronder beschreven aan de hand van een voorbeeld.

In deze illustratie nemen we het laatste element als spil. We kunnen zien dat de array achtereenvolgens is verdeeld rond het pivot-element totdat we een enkel element in de array hebben.

Nu presenteren we een illustratie van de Quicksort hieronder om het concept beter te begrijpen.

Illustratie

Laten we eens kijken naar een illustratie van het quicksort-algoritme. Beschouw de volgende array met het laatste element als draaipunt. Ook is het eerste element laag gelabeld en is het laatste element hoog.

hoe je een xml-bestand opent in word

Uit de illustratie kunnen we zien dat we de aanwijzers aan beide uiteinden van de array hoog en laag verplaatsen. Telkens wanneer lage punten naar het element groter zijn dan het draaipunt en hoge punten naar het element wijzen dat kleiner is dan het draaipunt, wisselen we de posities van deze elementen uit en verplaatsen we de lage en hoge wijzers in hun respectievelijke richtingen.

Dit wordt gedaan totdat de low en high pointers elkaar kruisen. Zodra ze elkaar kruisen, wordt het scharnierelement op de juiste positie geplaatst en wordt de array in tweeën verdeeld. Vervolgens worden beide sub-arrays onafhankelijk van elkaar gesorteerd met behulp van recursief quicksort.

C ++ Voorbeeld

Hieronder wordt de implementatie van het Quicksort-algoritme in C ++ gegeven.

Uitgang:

Invoerarray

12 23 3 43 51 35 19 45

Matrix gesorteerd met quicksort

3 12 19 23 35 43 45 51

Hier hebben we een paar routines die worden gebruikt om de array te partitioneren en quicksort recursief aan te roepen om de partitie te sorteren, de basis quicksort-functie en utility-functies om de array-inhoud weer te geven en de twee elementen dienovereenkomstig te wisselen.

Eerst noemen we de quicksort-functie met de invoerarray. Binnen de quicksort-functie noemen we de partitiefunctie. In de partitiefunctie gebruiken we het laatste element als het pivot-element voor de array. Zodra de pivot is bepaald, wordt de array in twee delen verdeeld en vervolgens wordt de quicksort-functie aangeroepen om beide sub-arrays onafhankelijk te sorteren.

Wanneer de quicksort-functie terugkeert, wordt de array zodanig gesorteerd dat het pivot-element op de juiste locatie staat en de elementen kleiner dan het pivot links van het pivot en de elementen groter dan het pivot rechts van het pivot.

c ++ ongedefinieerde referentiefout

Vervolgens zullen we het quicksort-algoritme in Java implementeren.

Java-voorbeeld

Uitgang:

Invoerarray

12 23 3 43 51 35 19 45

Array na sortering met quicksort

3 12 19 23 35 43 45 51

Ook in de Java-implementatie hebben we dezelfde logica gebruikt die we hebben gebruikt in de C ++ -implementatie. We hebben het laatste element in de array gebruikt omdat de pivot en quicksort op de array wordt uitgevoerd om het pivot-element op de juiste positie te plaatsen.

Complexiteitsanalyse van het Quicksort-algoritme

De tijd die quicksort nodig heeft om een ​​array te sorteren, is afhankelijk van de invoerarray en de partitiestrategie of -methode.

Als k het aantal elementen is dat kleiner is dan de pivot en n het totale aantal elementen is, dan kan de algemene tijd die quicksort in beslag neemt als volgt worden uitgedrukt:

T (n) = T (k) + T (n-k-1) + O (n)

Hier zijn T (k) en T (n-k-1) de tijd die recursieve oproepen nodig hebben en O (n) de tijd die nodig is om de oproep te partitioneren.

Laten we deze tijdcomplexiteit voor quicksort in detail analyseren.

# 1) In het ergste geval : Het ergste geval in de quicksort-techniek treedt meestal op wanneer we het laagste of hoogste element in de array als draaipunt selecteren. (In de bovenstaande illustratie hebben we het hoogste element als draaipunt geselecteerd). In een dergelijke situatie doet zich het ergste geval voor wanneer de te sorteren array al in oplopende of aflopende volgorde is gesorteerd.

Vandaar dat de bovenstaande uitdrukking voor de totale benodigde tijd verandert als:

T (n) = T (0) + T (n-1) + O (n) dat lost op Aan^twee​

# 2) Beste geval: Het beste geval voor quicksort doet zich altijd voor als het geselecteerde pivot-element het midden van de array is.

Dus de herhaling voor het beste geval is:

implementeren prioriteit wachtrij c ++

T (n) = 2T (n / 2) + O (n) = O (nlogn)

# 3) Gemiddeld geval: Om het gemiddelde geval voor quicksort te analyseren, moeten we alle array-permutaties in overweging nemen en vervolgens de tijd berekenen die elk van deze permutaties nodig heeft. In een notendop: de gemiddelde tijd voor quicksort wordt ook O (nlogn).

Hieronder worden de verschillende complexiteiten van de Quicksort-techniek gegeven:

We kunnen quicksort op veel verschillende manieren implementeren door de keuze van het pivot-element (midden, eerste of laatste) te veranderen, maar het ergste geval komt zelden voor bij quicksort.

3-weg Quicksort

In de originele quicksort-techniek selecteren we meestal een pivot-element en verdelen we de array vervolgens in sub-arrays rond dit pivot, zodat de ene sub-array bestaat uit elementen die kleiner zijn dan de pivot en een andere uit elementen die groter zijn dan de pivot.

Maar wat als we een pivot-element selecteren en er is meer dan één element in de array dat gelijk is aan pivot?

Bijvoorbeeld, overweeg de volgende array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Als we een eenvoudige quicksort uitvoeren op deze array en 4 selecteren als een pivot-element, dan repareren we slechts één exemplaar van element 4 en wordt de rest samen met de andere elementen verdeeld.

Als we in plaats daarvan een 3-way quicksort gebruiken, zullen we de array (l… r) als volgt in drie sub-arrays verdelen:

1. Array (l… i) - Hier is i de spil en deze array bevat minder elementen dan de spil.
2. Array (i + 1… j-1) - Bevat de elementen die gelijk zijn aan het draaipunt.
3. Array (j… r) - Bevat elementen die groter zijn dan het draaipunt.

Dus 3-way quicksort kan worden gebruikt als we meer dan één redundant element in de array hebben.

Gerandomiseerde Quicksort

De quicksort-techniek wordt gerandomiseerde quicksort-techniek genoemd wanneer we willekeurige getallen gebruiken om het pivot-element te selecteren. In gerandomiseerde quicksort wordt het 'central pivot' genoemd en het verdeelt de array zodanig dat elke kant ten minste ¼ elementen heeft.

De pseudo-code voor gerandomiseerde quicksort wordt hieronder gegeven:

In de bovenstaande code op “randomQuickSort”, in stap # 2 selecteren we het centrale draaipunt. In stap 2 is de kans dat het geselecteerde element het centrale draaipunt is ½. Daarom wordt verwacht dat de lus in stap 2 2 keer wordt uitgevoerd. Dus de tijdcomplexiteit voor stap 2 in gerandomiseerde quicksort is O (n).

Het gebruik van een lus om het centrale draaipunt te selecteren, is niet de ideale manier om een ​​willekeurige quicksort te implementeren. In plaats daarvan kunnen we willekeurig een element selecteren en het centrale draaipunt noemen of de array-elementen herschikken. De verwachte tijdcomplexiteit in het slechtste geval voor een willekeurig quicksort-algoritme is O (nlogn).

Quicksort versus samenvoegen sorteren

In dit gedeelte bespreken we de belangrijkste verschillen tussen Snel sorteren en Samenvoegen.

Gevolgtrekking

Zoals de naam zelf suggereert, is quicksort het algoritme dat de lijst snel sorteert dan enig ander sorteeralgoritme. Net als bij het samenvoegen, hanteert snel sorteren ook een verdeel en heers-strategie.

Zoals we al hebben gezien, verdelen we met behulp van snel sorteren de lijst in subarrays met behulp van het pivot-element. Vervolgens worden deze sub-arrays onafhankelijk gesorteerd. Aan het einde van het algoritme is de hele array volledig gesorteerd.

Quicksort is sneller en werkt efficiënt voor het sorteren van datastructuren. Quicksort is een populair sorteeralgoritme en heeft soms zelfs de voorkeur boven het samenvoegsorteeralgoritme.

In onze volgende tutorial zullen we meer in detail bespreken over Shell-sortering.

​ Bekijk hier de eenvoudige C ++ trainingsserie.

Aanbevolen literatuur

• MongoDB Sort () -methode met voorbeelden
• Unix-sorteeropdracht met syntaxis, opties en voorbeelden
• Sorteer samenvoegen in C ++ met voorbeelden
• Heap-sortering in C ++ met voorbeelden
• Shell-sortering in C ++ met voorbeelden
• Selectie sorteren in C ++ met voorbeelden
• Bubbelsortering in C ++ met voorbeelden
• Invoegsortering in C ++ met voorbeelden