|
Dit artikel is gepubliceerd op woensdag 28 april 2010 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 smallestkleinste waarde ongesorteerd deel = 21 => verwissel 21 en 88 [-sorted-] [-unsorted----------------------------------]
index 0 1 2 3 4
value 21 75 93 81 88
smallest
firstkleinste waarde ongesorteerd deel = 75 => verwissel 75 en 75 [-sorted------------] [-unsorted-----------------------]
index 0 1 2 3 4
value 21 75 93 81 88
first smallestDe 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 smallestkleinste 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 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 Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic 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 woensdag 28 april 2010 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
Visual Basic 2008 & 2010 Boeken
Berichten
| 
6. 
