shell sort c with examples
Shell-sorteertechniek in C ++: een compleet overzicht.
Shell-sortering wordt vaak genoemd als een verbetering ten opzichte van insertion-sortering. Bij invoegsortering nemen we incrementen met 1 om elementen te vergelijken en ze op hun juiste positie te plaatsen.
Bij shell-sortering wordt de lijst gesorteerd door deze op te splitsen in een aantal kleinere sublijsten. Het is niet nodig dat de lijsten opeenvolgende elementen bevatten. In plaats daarvan gebruikt de shell-sorteertechniek increment i, ook wel 'gap' genoemd, en gebruikt het om een lijst met elementen te maken die uit elkaar 'i' -elementen zijn.
Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.
hoe float in java te declareren
Wat je leert:
Algemeen algoritme
Het algemene algoritme voor shell-sortering wordt hieronder gegeven.
shell_sort (A, N)
waarbij A - lijst die moet worden gesorteerd; N - gap_size
set gap_size = N, vlag = 1
terwijl gap_size> 1 of flag = 1, herhaal
beginnen
set vlag = 0
stel gap_size = (gap_size + 1) / 2
einde
voor i = 0 tot i<(N-gap_size) repeat
beginnen
als A (i + gap_size)> A (i)
verwissel A (i + gap_size), A (i)
set vlag = 0
einde
einde
Dus in het bovenstaande algoritme stellen we eerst N in, wat de opening is voor het sorteren van array A met behulp van shell-sortering. In de volgende stap verdelen we de array in sub-arrays door de gap te gebruiken. Vervolgens sorteren we in de volgende stap elk van de sub-arrays zodat we aan het einde van de lus een gesorteerde array krijgen.
Laten we vervolgens een gedetailleerd voorbeeld bekijken om de shell-sortering beter te begrijpen met behulp van een picturale weergave.
Illustratie
Laten we de Shell-sortering illustreren met een voorbeeld.
Beschouw de volgende reeks van 10 elementen.
Als we een tussenruimte van 3 opgeven, hebben we de volgende sublijsten met elk element dat 3 elementen van elkaar verwijderd is. Vervolgens sorteren we deze drie sublijsten.
De gesorteerde sublijsten en de resulterende lijst die we verkrijgen na het combineren van de drie gesorteerde sublijsten worden hieronder weergegeven.
De bovenstaande array die we hebben verkregen na het samenvoegen van de gesorteerde subarrays, is bijna gesorteerd. Nu kunnen we invoegsortering op deze lijst uitvoeren en de hele array sorteren. Deze laatste stap wordt hieronder ter referentie weergegeven.
Zoals hierboven gezien, hadden we na het uitvoeren van shell-sortering en het samenvoegen van de gesorteerde sublijsten slechts drie zetten nodig om de lijst volledig te sorteren. We kunnen dus zien dat we het aantal stappen dat nodig is om de array te sorteren aanzienlijk kunnen verminderen.
De keuze van increment om sublijsten te maken is een unieke eigenschap van shell-sortering.
C ++ Voorbeeld
Laten we de implementatie van shell-sort in C ++ hieronder bekijken.
Uitgang:
Te sorteren matrix:
45 23 53 43 18 24 8 95101
Array na shell-sortering:
8 18 23 24 43 45 53 95101
We hebben dezelfde lijst gebruikt die we in de illustratie hebben gebruikt en we kunnen zien dat we in eerste instantie beginnen met het maken van twee sublijsten en vervolgens de kloof verder verkleinen. Zodra er sublijsten zijn gemaakt volgens het opgegeven gat, sorteren we elk van de sublijsten. Nadat alle sublijsten zijn gesorteerd, krijgen we de bijna gesorteerde lijst. Nu kan deze lijst worden gesorteerd met behulp van de basissortering voor invoegen, waarvoor zeer weinig zetten nodig zijn.
Laten we vervolgens shell-sortering implementeren met behulp van de Java-taal.
Java-voorbeeld
Uitgang:
Te sorteren matrix:
45 23 53 43 18 24 8 95101
Array na shell-sortering:
8 18 23 24 43 45 53 95101
We hebben dezelfde logica geïmplementeerd voor shell-sortering in zowel C ++ als Java-programma's. Dus zoals hierboven uitgelegd in het Java-programma, verdelen we de array eerst in subarrays en vervolgens sorteren we ze om een compleet gesorteerde array te verkrijgen.
Gevolgtrekking
Shell-sortering is het zeer efficiënte algoritme dat tot een verbetering komt ten opzichte van de invoegsortering.
Terwijl invoegsortering werkt door de elementen met 1 te verhogen, gebruikt shell-sortering de parameter 'gap' om de array op te delen in sub-arrays waarvan de elementen 'gap' uit elkaar liggen. Vervolgens kunnen we de individuele lijst sorteren met behulp van invoegsortering om de volledige gesorteerde reeks te verkrijgen.
Shell-sortering werkt sneller dan invoegsortering en er zijn minder bewegingen nodig om de array te sorteren in vergelijking met invoegsortering. Onze aanstaande tutorial zal alles onderzoeken over de heap-sorteertechniek voor het sorteren van gegevensstructuren.
Bezoek hier om C ++ vanaf het begin te leren.
Aanbevolen literatuur
- Selectie sorteren in C ++ met voorbeelden
- MongoDB Sort () -methode met voorbeelden
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- Bubbelsortering in C ++ met voorbeelden
- Invoegsortering in C ++ met voorbeelden
- Sorteer samenvoegen in C ++ met voorbeelden
- Heap-sortering in C ++ met voorbeelden
- Snel sorteren in C ++ met voorbeelden