introduction sorting techniques c
Lijst met de verschillende sorteertechnieken in C ++.
Sorteren is een techniek die wordt geïmplementeerd om de gegevens in een specifieke volgorde te rangschikken. Sorteren is vereist om ervoor te zorgen dat de gegevens die we gebruiken in een bepaalde volgorde staan, zodat we gemakkelijk het vereiste stuk informatie uit de stapel gegevens kunnen halen.
Als de gegevens onverzorgd en ongesorteerd zijn en we een bepaald stuk informatie willen, zullen we deze elke keer een voor een moeten doorzoeken om de gegevens op te halen.
Lees de Easy C ++ Training Series door.
Het is dus altijd raadzaam dat we onze gegevens in een specifieke volgorde bewaren, zodat het ophalen van informatie, evenals andere bewerkingen die op de gegevens worden uitgevoerd, gemakkelijk en efficiënt kunnen worden uitgevoerd.
We slaan gegevens op in de vorm van records. Elk record bestaat uit een of meer velden. Als elk record een unieke waarde heeft van een bepaald veld, noemen we dit een sleutelveld. Bijvoorbeeld, in een klas kan Roll No een uniek veld of een sleutelveld zijn.
wat is bètatesten en hoe wordt het gebruikt
We kunnen de gegevens op een bepaald sleutelveld sorteren en deze vervolgens in oplopende / oplopende volgorde of in aflopende / aflopende volgorde rangschikken.
Evenzo bestaat in een telefoonwoordenboek elk record uit de naam van een persoon, adres en telefoonnummer. Hierin is het telefoonnummer een uniek of sleutelveld. We kunnen de gegevens van het woordenboek op dit telefoonveld sorteren. Als alternatief kunnen we gegevens ook numeriek of alfanumeriek sorteren.
Wanneer we de te sorteren gegevens in het hoofdgeheugen zelf kunnen aanpassen zonder dat er een ander hulpgeheugen nodig is, noemen we dat Interne sortering
Aan de andere kant, als we een hulpgeheugen nodig hebben voor het opslaan van tussentijdse gegevens tijdens het sorteren, noemen we de techniek als Externe sortering
In deze tutorial zullen we de verschillende sorteertechnieken in C ++ in detail leren.
Wat je leert:
Sorteertechnieken in C ++
C ++ ondersteunt verschillende sorteertechnieken zoals hieronder vermeld.
Bubble Sorteren
Bubble sort is de eenvoudigste techniek waarbij we elk element vergelijken met het aangrenzende element en de elementen verwisselen als ze niet in orde zijn. Op deze manier wordt aan het einde van elke iteratie (pass genoemd) het zwaarste element aan het einde van de lijst opborreld.
Hieronder is een voorbeeld van bellen sorteren.
Te sorteren matrix:
Zoals hierboven te zien is, omdat het een kleine array is en bijna gesorteerd, zijn we erin geslaagd om in een paar passen een volledig gesorteerde array te krijgen.
Laten we de Bubble Sort-techniek implementeren in C ++.
Uitgang:
Invoerlijst ...
10 2 0 43 12
Gesorteerde elementenlijst ...
0 2 10 12 43
Zoals blijkt uit de uitvoer, wordt in de belsorteertechniek bij elke doorgang het zwaarste element naar het einde van de reeks geborreld, waardoor de reeks volledig wordt gesorteerd.
Selectie sorteren
Het is een eenvoudige maar gemakkelijk te implementeren techniek waarbij we het kleinste element in de lijst vinden en op de juiste plaats plaatsen. Bij elke doorgang wordt het volgende kleinste element geselecteerd en op de juiste positie geplaatst.
Laten we dezelfde array nemen als in het vorige voorbeeld en Selectie sorteren uitvoeren om deze array te sorteren.
Zoals te zien is in de bovenstaande illustratie, nemen we voor het aantal N-elementen N-1-passen om de array volledig te sorteren. Aan het einde van elke doorgang wordt het kleinste element in de array op de juiste positie in de gesorteerde array geplaatst.
Laten we vervolgens de Selection Sort implementeren met C ++.
Uitgang:
Invoerlijst met te sorteren elementen
12 45 8 15 33
Gesorteerde lijst met elementen is
8 12 15 33 45
Bij selectiesortering wordt bij elke doorgang het kleinste element in de array op de juiste positie geplaatst. Daarom krijgen we aan het einde van het sorteerproces een volledig gesorteerde array.
Invoegsortering
Invoegsortering is een techniek waarbij we starten vanaf het tweede element van de lijst. We vergelijken het tweede element met het vorige (1st) element en plaats het op de juiste plaats. In de volgende stap vergelijken we het voor elk element met al zijn voorgaande elementen en voegen we dat element op de juiste plaats in.
De bovenstaande drie sorteertechnieken zijn eenvoudig en gemakkelijk toe te passen. Deze technieken presteren goed wanneer de lijst kleiner is. Naarmate de lijst groter wordt, werken deze technieken niet zo efficiënt.
De techniek zal duidelijk worden door de volgende illustratie te begrijpen.
De te sorteren array is als volgt:
Nu vergelijken we voor elke doorgang het huidige element met al zijn voorgaande elementen. Dus in de eerste doorgang beginnen we met het tweede element.
We hebben dus N aantal passages nodig om een array met N aantal elementen volledig te sorteren.
Laten we de Insertion Sort-techniek implementeren met C ++.
Uitgang:
Invoerlijst is
12 4 3 1 15
Gesorteerde lijst is
1 3 4 12 15
De bovenstaande uitvoer toont de volledige gesorteerde array met behulp van invoegsortering.
Snel sorteren
Quicksort is het meest efficiënte algoritme dat kan worden gebruikt om de gegevens te sorteren. Deze techniek maakt gebruik van de 'verdeel en heers' -strategie waarin het probleem wordt opgedeeld in verschillende deelproblemen en na het oplossen van deze deelproblemen afzonderlijk worden samengevoegd tot een volledig gesorteerde lijst.
Bij quicksort verdelen we eerst de lijst rond het pivot-element en vervolgens plaatsen we de overige elementen op hun juiste posities volgens het pivot-element.
Zoals te zien is in de bovenstaande illustratie, verdelen we in de Quicksort-techniek de array rond een scharnierelement, zodat alle elementen die kleiner zijn dan het draaipunt zich aan de linkerkant bevinden, welke van die groter dan het draaipunt aan de rechterkant zijn. Vervolgens nemen we deze twee arrays onafhankelijk van elkaar op en sorteren ze en voegen ze samen of veroveren ze om een resulterende gesorteerde array te krijgen.
De sleutel tot Quicksort is de selectie van het pivot-element. Het kan het eerste, laatste of het middelste element van de array zijn. De eerste stap na het selecteren van het pivot-element is om het pivot in de juiste positie te plaatsen, zodat we de array op de juiste manier kunnen verdelen.
Laten we de Quick Sort-techniek implementeren met C ++.
Uitgang:
Invoerarray
12 23 3 43 51
Array gesorteerd met Quicksort
3 12 23 43 51
In de quicksort-implementatie hierboven hebben we een partitieroutine die wordt gebruikt om de invoerarray te partitioneren rond een pivot-element dat het laatste element in de array is. Vervolgens noemen we de quicksort-routine recursief om de sub-arrays individueel te sorteren zoals weergegeven in de afbeelding.
Samenvoegen Sorteren
Dit is een andere techniek die de 'Verdeel en heers' -strategie gebruikt. Bij deze techniek verdelen we de lijst eerst in gelijke helften. Vervolgens voeren we de samenvoegsorteertechniek op deze lijsten onafhankelijk uit, zodat beide lijsten worden gesorteerd. Ten slotte voegen we beide lijsten samen om een volledig gesorteerde lijst te krijgen.
Samenvoegen en snel sorteren zijn sneller dan de meeste andere sorteertechnieken. Hun prestaties blijven intact, zelfs als de lijst groter wordt.
Laten we eens kijken naar een illustratie van de Merge Sort-techniek.
In de bovenstaande illustratie zien we dat de samenvoegsorteertechniek de oorspronkelijke array herhaaldelijk verdeelt in subarrays totdat er slechts één element in elke subarray is. Zodra dit is gebeurd, worden de subarrays onafhankelijk van elkaar gesorteerd en samengevoegd om een volledig gesorteerde array te vormen.
Laten we vervolgens Merge Sort implementeren met de taal C ++.
Uitgang:
Voer het aantal te sorteren elementen in: 5
Voer 5 elementen in om te sorteren: 10 21 47 3 59
Gesorteerde array
3 10 21 47 59
Shell Sorteren
Shell-sortering is een uitbreiding van de invoegsorteertechniek. Bij invoegsortering behandelen we alleen het volgende element, terwijl we bij shell-sortering een increment of een tussenruimte bieden waarmee we kleinere lijsten van de bovenliggende lijst maken. De elementen in de sublijsten hoeven niet aaneengesloten te zijn, maar zijn meestal ‘gap_value’ van elkaar verwijderd.
Shell-sortering werkt sneller dan de invoegsortering en vereist minder verplaatsingen dan die van de invoegsortering.
Als we een tussenruimte van geven, dan hebben we de volgende sublijsten met elk element dat 3 elementen van elkaar verwijderd is.
Vervolgens sorteren we deze drie sublijsten.
De bovenstaande array die we hebben verkregen na het samenvoegen van de gesorteerde sub-arrays is bijna gesorteerd. Nu kunnen we invoegsortering op deze array uitvoeren om de hele array te sorteren.
We zien dus dat als we de array in sublijsten verdelen met de juiste incrementering en ze vervolgens samenvoegen, we de bijna gesorteerde lijst krijgen. De invoegsorteringstechniek op deze lijst kan worden uitgevoerd en de array wordt in minder bewegingen gesorteerd dan de oorspronkelijke invoegsortering.
Hieronder wordt de implementatie van de Shell Sort in C ++ gegeven.
Uitgang:
Te sorteren matrix:
45 23 53 43 18
Array na shell-sortering:
18 23 43 45 53
Shell-sortering werkt dus als een enorme verbetering ten opzichte van invoegsortering en neemt niet eens de helft van het aantal stappen om de array te sorteren.
Heap Sorteren
Heapsort is een techniek waarbij heap-datastructuur (min-heap of max-heap) wordt gebruikt om de lijst te sorteren. We construeren eerst een heap uit de ongesorteerde lijst en gebruiken de heap ook om de array te sorteren.
Heapsort is efficiënt, maar niet zo snel als de sortering Samenvoegen.
Zoals getoond in de bovenstaande illustratie, construeren we eerst een maximale heap uit de array-elementen die moeten worden gesorteerd. Vervolgens doorkruisen we de hoop en wisselen het laatste en eerste element om. Op dit moment is het laatste element al gesorteerd. Daarna bouwen we weer een maximale hoop uit de resterende elementen.
Doorkruis opnieuw de hoop en verwissel de eerste en laatste elementen en voeg het laatste element toe aan de gesorteerde lijst. Dit proces wordt voortgezet totdat er nog maar één element in de heap overblijft dat het eerste element van de gesorteerde lijst wordt.
Laten we nu Heap Sort implementeren met C ++.
Uitgang:
Invoerarray
4 17 3 12 9
Gesorteerde array
3 4 9 12 17
Tot nu toe hebben we alle belangrijke sorteertechnieken kort besproken met een illustratie. We zullen elk van deze technieken in detail leren in onze volgende tutorials, samen met verschillende voorbeelden om elke techniek te begrijpen.
Gevolgtrekking
Sorteren is vereist om de gegevens gesorteerd en in de juiste volgorde te houden. Ongesorteerd en onverzorgd kan er langer over doen om toegang te krijgen en kan dus de prestaties van het hele programma beïnvloeden. Dus voor alle bewerkingen met betrekking tot gegevens zoals toegang, zoeken, manipulatie, enz., Moeten de gegevens worden gesorteerd.
Bij het programmeren worden veel sorteertechnieken gebruikt. Elke techniek kan worden gebruikt, afhankelijk van de datastructuur die we gebruiken of de tijd die het algoritme nodig heeft om de data of geheugenruimte te sorteren die het algoritme in beslag neemt om de data te sorteren. De techniek die we gebruiken, hangt ook af van de datastructuur die we sorteren.
De sorteringstechnieken stellen ons in staat om onze datastructuren in een specifieke volgorde te sorteren en de elementen in oplopende of aflopende volgorde te rangschikken. We hebben de sorteertechnieken gezien zoals Bubble sort, Selection sort, Insertion sort, Quicksort, Shell sort, Merge sort en Heap sort. Bubble sort en Selection sort zijn eenvoudiger en gemakkelijker te implementeren.
In onze volgende tutorials zullen we elk van de bovengenoemde sorteertechnieken in detail bekijken.
Klik hier voor de gratis C ++ cursus.
Aanbevolen literatuur
- Heap Sorteren in C ++ met voorbeelden
- Sorteer samenvoegen in C ++ met voorbeelden
- Invoegsortering in C ++ met voorbeelden
- JMeter Video 1: Inleiding, JMeter downloaden en installeren
- Inleiding tot de programmeertaal van Java - videozelfstudie
- Python introductie en installatieproces
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- MongoDB Sort () -methode met voorbeelden