|
Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
We hebben gezien dat het op "binary search"-wijze doorzoeken van een array op een bepaalde waarde veel efficiënter kan zijn dan dit via een "linear search" te gaan doen.
Een vereiste voor de "binary search" is echter wel dat de elementen in de array gesorteerd zijn.
Het kan zelfs efficiënter zijn ( zeker wanneer je meerdere waarden in een array moet opzoeken ) om een array eerst te gaan sorteren, alvorens er waarden via de "binary search" in te gaan opzoeken.
De 3 sorteermethoden die in dit topic besproken worden zijn allen "in-place" sorteermethoden. Waarbij de elementen in de tabel zelf verplaatst worden, en dus geen extra tabellen gebruikt worden. Deze sorteermethoden zijn bijgevolg goed om het gebruikte geheugen te beperken.
We gaan er steeds vanuit dat een array van 5 elementen met onderstaande numerieke waarden van klein naar groot gaan sorteren. Maar alle vermelde sorteermethoden zullen ook functioneren voor andere datatypes en sorteer-principes.
Ongesorteerd tabel : index 0 1 2 3 4
value 88 75 93 81 21 7.4.1. Selection SortWe beginnen met de "selection sort". Hierin wordt met twee denkbeeldige onderdelen van de array gewerkt, een ongesorteerd en een gesorteerd deel.
Als volgt gaan we te werk :
(1) bepaal het kleinste element ( het eerste te plaatsen element ) in het ongesorteerde deel
(2) verwissel het eerste element van het ongesorteerde deel met het kleinste element van het ongesorteerde deel
Zo bekom je een ongesorteerd deel die 1 element kleiner is. Herhaal nu bovenstaande 2 stappen zolang je een ongesorteerd deel hebt die meer dan 1 element bevat.
We starten dus met een volledig ongesorteerde array : [-unsorted---------------------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21
first smallest kleinste waarde ongesorteerd deel = 21 => verwissel 21 en 88 [-sorted-] [-unsorted----------------------------------]
index 0 1 2 3 4
value 21 75 93 81 88
smallest
first kleinste waarde ongesorteerd deel = 75 => verwissel 75 en 75 [-sorted------------] [-unsorted-----------------------]
index 0 1 2 3 4
value 21 75 93 81 88
first smallest De verwisseling is hier nutteloos ( maar kan geen kwaad ).
kleinste waarde ongesorteerd deel = 81 => verwissel 81 en 93 [-sorted-----------------------] [-unsorted------------]
index 0 1 2 3 4
value 21 75 81 93 88
first smallest kleinste waarde ongesorteerd deel = 88 => verwissel 88 en 93 [-sorted----------------------------------] [-unsorted-]
index 0 1 2 3 4
value 21 75 81 88 93 Als het ongesorteerde deel slechts 1 element bevat is ook dat deel eigenlijk gesorteerd, want 1 element kan nooit op de ongesorteerd positie ten opzichte van zichzelf zitten. Dus de volledige array is nu gesorteerd. Visual Basic 2010 Broncode Module SelectionSortExample Sub Main() Dim count As Integer = 5 Dim upperbound As Integer = count - 1 Dim numbers(upperbound) As Integer Dim index As Integer For index = 0 To upperbound numbers(index) = (count ^ index) * 93 Mod 97 - (count \ (index + 1)) Next Console.Write( "unsorted array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.WriteLine() Dim unsortedCount As Integer = count Do While unsortedCount > 1 Dim startIndexUnsortedPart As Integer = count - unsortedCount Dim indexSmallestElement As Integer = startIndexUnsortedPart For index = startIndexUnsortedPart To upperbound If numbers(index) < numbers(indexSmallestElement) Then indexSmallestElement = index End If Next Dim backup As Integer = numbers(indexSmallestElement) numbers(indexSmallestElement) = numbers(startIndexUnsortedPart) numbers(startIndexUnsortedPart) = backup unsortedCount -= 1 Console.Write( "temporary array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.WriteLine() Loop Console.Write( "sorted array : ") For index = 0 To upperbound Console.Write(numbers(index) & " ") Next Console.ReadLine() End SubEnd ModuleDownload Visual Basic 2010 Broncode Download Visual C# Sourcecode
Console Application Output unsorted array : 88 75 93 81 21
temporary array : 21 75 93 81 88
temporary array : 21 75 93 81 88
temporary array : 21 75 81 93 88
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
| 
6. 
