Dit zijn voorbeelden van algoritmen om een stapel kaarten met veel verschillende getallen te sorteren, zodat de getallen op volgorde liggen.
De spelers beginnen met een stapel kaarten die nog niet gesorteerd zijn.
Eerste algoritme
Dit algoritme doorloopt de stapel kaarten, één kaart per keer. Deze kaart wordt vergeleken met de volgende kaart op de stapel. Merk op dat deze positie pas in stap 6 verandert. Dit algoritme heet bubble sort. Het is langzaam.
- Als de stapel kaarten leeg is, of als er maar één kaart op ligt, is hij gesorteerd; je bent klaar.
- Pak de stapel kaarten. Kijk naar de eerste kaart (de bovenste) van de stapel.
- De kaart waar je naar kijkt is kaart A. De positie waar kaart A zich momenteel bevindt, is in stapel P.
- Als er na kaart A geen kaarten meer in de stapel zitten, ga dan naar stap 8.
- De volgende kaart op de stapel is kaart B.
- Als kaart B een lager nummer heeft dan kaart A, verwissel dan de posities van kaarten A en B. Onthoud dat je dit gedaan hebt. Als je kaarten verwisselt, verander dan niet de positie P.
- Als er nog een kaart in de stapel zit na positie P, kijk er dan naar; ga terug naar stap 3.
- Als u in de laatste run geen kaarten van plaats heeft verwisseld, bent u klaar; de stapel kaarten is gesorteerd.
- Ga anders terug naar stap 2.
Stap-voor-stap voorbeeld
Laten we een stapel kaarten nemen met de getallen "5 1 4 2 8", en deze sorteren van het kleinste getal naar het grootste met behulp van dit algoritme. In elke stap vergelijkt het algoritme de vetgedrukte elementen. De bovenkant van de stapel kaarten ligt aan de linkerkant.
Eerste doorgang:
( 5 1 4 2 8 ) → {\displaystyle \to } 
( 1 5 4 2 8 ) Hier vergelijkt het algoritme de eerste twee elementen, en verwisselt ze.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 2 8 )(
1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 ) Deze elementen staan al op volgorde, dus het algoritme verwisselt ze niet.
Tweede pass:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )(
1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Nu, de stapel kaarten is al gesorteerd, maar ons algoritme weet dit niet. Het algoritme heeft een hele pas nodig zonder enige verwisseling om te weten dat het gesorteerd is.
Derde pass:
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )(
1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → {\displaystyle \to } ( 1 2 4 5 8 )
Tenslotte is de array gesorteerd, en kan het algoritme stoppen.
Geschiedenis
Dit is een eenvoudig te begrijpen algoritme voor sorteren. Computerwetenschappers noemden het Bubble sort, omdat kleinere elementen naar de top zullen stijgen, waarbij hun positie bij elke run verandert. Helaas is het algoritme niet erg goed, want het heeft veel tijd nodig (veel passes door de stapel kaarten) om te sorteren.
Tweede algoritme
Dit algoritme maakt gebruik van een ander idee. Soms is het oplossen van een probleem moeilijk, maar kan het probleem veranderd worden zodat het bestaat uit eenvoudiger problemen die gemakkelijker op te lossen zijn. Dit wordt recursie genoemd. Het is moeilijker te begrijpen dan het eerste voorbeeld, maar het zal een beter algoritme opleveren.
Basisidee
- Als er geen kaarten op de stapel liggen, of als er maar één kaart op ligt, is hij gesorteerd, en ben je klaar.
- Verdeel de stapel kaarten in twee helften van ongeveer dezelfde grootte. Als er een oneven aantal kaarten is, zal een van de twee stapels een kaart meer hebben dan de andere.
- Sorteer elk van de twee stapels volgens dit algoritme (Begin voor elke stapel bij punt 1 van deze lijst).
- Voeg de twee gesorteerde stapels samen, zoals hieronder beschreven.
- Het resultaat is een gesorteerde stapel kaarten. U bent klaar.
Twee stapels samenvoegen
Dit werkt met twee stapels kaarten. Een ervan heet A, de andere heet B. Er is een derde stapel die aan het begin leeg is, genaamd C. Aan het eind zal deze de uitkomst bevatten.
- Als stapel A of B leeg is, leg je alle kaarten van de stapel die niet leeg is bovenop stapel C; je bent klaar, stapel C is het resultaat van de samensmelting. (Opmerking: neem de hele stapel en leg die op stapel C; als u dit kaart voor kaart doet, verandert de volgorde en werkt het niet zoals het hoort).
- Kijk naar de bovenste kaarten van stapel A en stapel B. Leg de kaart met het laagste nummer bovenop stapel C. Als stapel C geen kaarten bevatte, zit er nu één kaart in.
- Als stapel A of stapel B kaarten over heeft, ga dan terug naar stap 1 om ze te sorteren.
Geschiedenis
John von Neumann ontwikkelde dit algoritme in 1945. Hij noemde het niet Sorteren op getallen, hij noemde het Mergesort. Het is een zeer goed algoritme voor sorteren, vergeleken met andere.
Derde algoritme
Het eerste algoritme doet er veel langer over om de kaarten te sorteren dan het tweede, maar het kan worden verbeterd (beter gemaakt). Als je naar bubble sort kijkt, zie je dat kaarten met hoge getallen vrij snel van de top van de stapel komen, maar dat kaarten met lage getallen onder aan de stapel er lang over doen om naar de top te komen. Om het eerste algoritme te verbeteren is hier het idee:
In plaats van twee kaarten te vergelijken die naast elkaar liggen, wordt er aan het begin een 'speciale' kaart gekozen. Alle andere kaarten worden dan vergeleken met deze kaart.
- We beginnen met een stapel A. Er zijn twee andere stapels B en C, die later zullen worden aangemaakt.
- Als stapel A geen kaarten heeft, of slechts één kaart, dan is het sorteren klaar.
- Er wordt een kaart gekozen van stapel A, zo mogelijk willekeurig. Dit wordt een pivot genoemd.
- Alle overgebleven kaarten van stapel A worden vergeleken met deze spil. Kaarten met een kleiner getal gaan naar stapel B, die met een gelijk of groter getal gaan naar stapel C.
- Als er kaarten in de stapels B of C zitten, moeten deze stapels met hetzelfde algoritme gesorteerd worden (Begin bij pos 1 van deze lijst voor zowel stapel B als stapel C om de beurt).
- Klaar. De gesorteerde stapel kaarten heeft eerst de gesorteerde stapel B, dan de spil, en dan de gesorteerde stapel C.
Geschiedenis
Dit algoritme is ontwikkeld door C.A.R. Hoare in 1960. Het is een van de meest gebruikte algoritmen voor sorteren vandaag de dag. Het wordt Quicksort genoemd.
