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 Aantwee
# 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:
Tijdscomplexiteit in het ergste geval | O (n 2) | |
stabiliteit | Niet stabiel omdat twee elementen met dezelfde waarden niet in dezelfde volgorde worden geplaatst. | Stabiel - twee elementen met dezelfde waarden verschijnen in dezelfde volgorde in de gesorteerde uitvoer. |
Tijdscomplexiteit in het beste geval | O (n * log n) | |
Gemiddelde tijdcomplexiteit | O (n * log n) | |
Complexiteit van de ruimte | O (n * log n) |
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:
- Array (l… i) - Hier is i de spil en deze array bevat minder elementen dan de spil.
- Array (i + 1… j-1) - Bevat de elementen die gelijk zijn aan het draaipunt.
- 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.
Vergelijkingsparameter | Snel sorteren | Sorteer samenvoegen |
---|---|---|
verdeling | De array is gepartitioneerd rond een scharnierelement en hoeft niet altijd in twee helften te worden verdeeld. Het kan in elke verhouding worden verdeeld. | De array is opgedeeld in twee helften (n / 2). |
Complexiteit in het ergste geval | O (n 2) - in het ergste geval zijn veel vergelijkingen vereist. | O (nlogn) - hetzelfde als het gemiddelde geval |
Gegevens stellen gebruik in | Werkt niet goed met grotere gegevenssets. | Werkt goed met alle datasets, ongeacht de grootte. |
Extra ruimte | Op zijn plaats - heeft geen extra ruimte nodig. | Niet op zijn plaats - heeft extra ruimte nodig om de hulparray op te slaan. |
Sorteermethode | Intern - gegevens worden gesorteerd in het hoofdgeheugen. | Extern - gebruikt extern geheugen voor het opslaan van gegevensarrays. |
Efficiëntie | Sneller en efficiënter voor lijsten met kleine afmetingen. | Snel en efficiënt voor grotere lijsten. |
Arrays / gekoppelde lijsten | Meer de voorkeur voor arrays. | Werkt goed voor gekoppelde lijsten. |
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