|
Dit artikel is gepubliceerd op woensdag 28 april 2010 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.
De laatste sorteermethode die we hier gaan bespreken is de "insertion sort".
Wederom wordt verondersteld een ongesorteerd en gesorteerd deel in de array. Steeds wordt een waarde uit het ongesorteerde deel op de juiste positie van het gesorteerde deel ingevoegd.
Meteen starten we hier met dezelfde getallenreeks, met als verschil dat we reeds starten met een gesorteerd deel die 1 element bevat. [-sorted-] [-unsorted----------------------------------]
index 0 1 2 3 4
value 88 75 93 81 21 Het eerste element van het ongesorteerde deel ( 75 ) wordt eruit genomen en we verschuiven vervolgens alle elementen van het gesorteerde deel ( startende bij het laatste element ) 1 positie op zolang dat element groter is dan het te-sorteren-getal ( 75 ).
En het te-sorteren-getal komt op de positie van het laatste verschoven element.
88 wordt hier dus naar achter geschoven. En 75 komt op index 0 ( de index van het laatste verschoven element ) terecht. [-sorted------------] [-unsorted-----------------------]
index 0 1 2 3 4
value 75 88 93 81 21 Dezelfde acties gaan we ondernemen totdat alle elementen van het ongesorteerde deel opgenomen zijn in het gesorteerde deel.
Het eerste element van het ongesorteerde deel ( 93 ) wordt eruit genomen en we verschuiven alle elementen van het gesorteerde deel 1 positie op zolang dat element groter is. 88 is niet groter dan 93, dus hier zullen geen elementen verschoven worden, dus bekomen we opnieuw ( met 93 nu wel reeds behorende tot het gesorteerde deel ) : [-sorted-----------------------] [-unsorted------------]
index 0 1 2 3 4
value 75 88 93 81 21 81 nemen we eruit. 93 is groter dan 81 => 93 een positie opschuiven. 88 is groter dan 81 => 88 een positie opschuiven.
75 is niet groter dan 81 dus blijft staan, index 1 was de positie van het laatst verschoven element, dus daarop komt 81 nu terecht : [-sorted----------------------------------] [-unsorted-]
index 0 1 2 3 4
value 75 81 88 93 21 Enkel nog 21 moet op de juiste plaats worden ingevoegd, alle elementen uit het gesorteerde deel zijn groter, dus allen zullen ze worden opgeschoven. 21 zal dan vooraan de tabel terecht komen, en de volledig tabel is gesorteerd : [-sorted-----------------------------------------------]
index 0 1 2 3 4
value 21 75 81 88 93 Visual Basic Broncode Module InsertionSortExample
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 - 1
Do Until unsortedCount = 0
Dim startIndexUnsortedPart As Integer = count - unsortedCount
Dim backup As Integer = numbers(startIndexUnsortedPart)
index = startIndexUnsortedPart - 1
Do While index >= 0 AndAlso numbers(index) > backup
numbers(index + 1) = numbers(index)
index -= 1
Loop
numbers(index + 1) = 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 : 75 88 93 81 21
temporary array : 75 88 93 81 21
temporary array : 75 81 88 93 21
temporary array : 21 75 81 88 93
sorted array : 21 75 81 88 93 7.6.1. Voorgedefinieerde Sorteermethoden - Quick SortDe meeste programmeertalen beschikken reeds over voorgedefinieerde functionaliteiten voor het sorteren van tabellen. Hier is dit niet anders. Visual Basic Broncode Module Example
Sub Main()
Dim count As Integer = 5
Dim upperbound As Integer = count - 1
Dim numbers(upperbound) As Integer
Dim index As Integer
Dim random As Random = New Random
For index = 0 To upperbound
numbers(index) = random.Next(1, 101)
Next
Console.Write("unsorted array : ")
For index = 0 To upperbound
Console.Write(numbers(index) & " ")
Next
Console.WriteLine()
Array.Sort(numbers)
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 : 24 37 88 82 46
sorted array : 24 37 46 82 88 De shared method Sort uit de klasse Array wordt hier gebruikt om de tabel numbers te sorteren.
Deze functionaliteit zal een "Quick Sort" toepassen op de tabel, deze heeft een performantie die nog beter is dan de hierboven behandelde sorteermethoden. Verderop meer informatie over de "Quick Sort" en over klassen en hun methoden.
Men ziet in bovenstaand voorbeeld overigens ook hoe je van een voorgedefinieerde functionaliteit gebruik kunt maken voor het ophalen van een willekeurig getal.
Dit kan aan de hand van de Next method van een object van het type Random. Deze method verwacht de minimumwaarde ( inclusief ) en maximumwaarde ( exclusief ) van het bereik waaruit een willekeurig getal moet opgeleverd worden. Verderop meer informatie over het gebruik van deze klasse Random.
Als programmeur zal je dus zelden of nooit een algoritme moeten definiëren voor het sorteren van de elementen van een tabel. Men kan immers gewoon van de hiervoor voorgedefinieerde functionaliteiten gebruik maken.
Indien men met collecties zit die niet bestaan uit tabellen, zal het echter vaak toch nog nodig zijn zelf dergelijk sorteeralgoritme te definiëren.  Terug naar boven
7.6.2. Performantie van SorteermethodenAls de performantie van de van de verschillende opgesomde sorteermethoden bekijken ( naar aantal vergelijkingen toe ), dan zou je bij het sorteren van 5 elementen met de "selection sort" steeds eerst 4 elementen met elkaar moeten vergelijken ( om het kleinste element te vinden ), dan 3 elementen en dan 2 elementen. With N elements : Maximum comparisons
if N = 5 : 4+3+2 = 9
if N = 10 : 9+8+7+6+5+4+3+2 = 44
if N = 20 : 19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2 = 189
generally : ( ( (N - 1) + 2 ) * (N - 2) ) / 2
or : ( ( N + 1 ) * (N - 2) ) / 2
or : ( N² + N - 2N - 2 ) / 2
or : ( N² - N - 2 ) / 2 Performantie van "selection sort" uitgedrukt in big-O-notatie :
"O((N^2-N-2)/2)" of vereenvoudigd ( constante factoren verwijderd, kleinere factoren genegeerd ) : "O(N^2)"
Ook bij de "bubble sort" gaan we steeds bij 5 elementen eerst 4 keer opeenvolgende elementen vergelijken, dan 3 keer opeenvolgende elementen vergelijken en dan nog 2 keer opeenvolgende elementen vergelijken.
Dus ook de performantie van de "bubble sort" uitgedrukt in big-O-notatie is steeds : "O(N^2)"
Bij de "insertion sort" dan gaan we bij het sorteren van 5 elementen eerst maximaal 1 element vergelijken ( om al dan niet te verschuiven indien dat element verderop gesorteerd moet worden ), dan maximaal 2 elementen, dan maximaal 3 en ten laatste maximaal 4.
Opnieuw hebben we dus in het slechtste geval een "quadratic running time" :
"O(N^2)".
Maar in het beste geval ( als de array reeds gesorteerd zou zijn ) hebben we steeds maximaal 1 vergelijking, dus een "linear running time" ( een linear verband tussen het aantal elementen en aantal vergelijkingen ) : "O(N)".
"Insertion sort" is bijgevolg ook de meest performante, hierbij zal - in tegenstelling tot de "selection-" en "bubble sort" - niet steeds een "quadratic running time" nodig zijn om dit algoritme uit te voeren. Terug naar boven 7.6.3. OefeningOpgave :
Vul onderstaande code aan om een programma te maken die functioneert zoals onderstaand programmaverloop.
Hou de munteenheden steeds gesorteerd bij. Bij de invoer van een munteenheid wordt de conversiefactor van deze munteenheid via de binary search methode opgezocht. Bij het toevoegen van een munteenheid en zijn conversie-factor worden deze via de insertion sort methode toegevoegd.
Bemerk dat Strings ook vergelijkbaar zijn met de operatoren <, >, <= en >=. Bijvoorbeeld zal de expressie "ABC" < "ABD" naar True evalueren, gezien "ABC" alfabetisch voor "ABD" komt. Visual Basic Broncode Module ExerciseTask
Sub Main()
Dim count As Integer = 10
Dim currencies As String() = {"ATS", "DEM", "ESP", "FIM", "FRF", _
"IEP", "ITL", "LUF", "NLG", "PTE"}
Dim conversionValues As Decimal() = {13.7603, 1.95583, 166.386, _
5.94573, 6.55957, 0.787564, _
1936.27, 40.3399, 2.20371, 200.482}
Do
Console.Write("Currencies : ")
Dim index As Integer
For index = 0 To count - 2
Console.Write(currencies(index) & " / ")
Next
Console.WriteLine(currencies(index))
Console.Write("Currency ? : ")
Dim currency As String = Console.ReadLine()
Dim found As Boolean
If found Then
Else
Console.Write("Add Currency ( Y/N ) ? : ")
Dim addCurrency As Char = Console.ReadLine()
If addCurrency = "y"c OrElse addCurrency = "Y"c Then
Console.Write("Conversion Value " & currency & _
" ( = 1 EUR ) ? : ")
Dim conversionValue As Decimal = Console.ReadLine()
End If
End If
Loop
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
Visual Basic Output Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : DEM
Amount DEM ? : 1,95583
Conversion : 1,95583 DEM = 1 EUR
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Add Currency ( Y/N ) ? : n
Currencies : ATS / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Add Currency ( Y/N ) ? : y
Conversion Value BEF ( = 1 EUR ) ? : 40,3399
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEE
Add Currency ( Y/N ) ? : N
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : BEF
Amount BEF ? : 40,3399
Conversion : 40,3399 BEF = 1 EUR
Currencies : ATS / BEF / DEM / ESP / FIM / FRF / IEP / ITL / LUF / NLG / PTE
Currency ? : De invoer van een "currency" en de daaraan gekoppelde actie, wordt eindeloos herhaald. Oplossing : Visual Basic Broncode Module ExerciseSolution
Sub Main()
Dim count As Integer = 10
Dim currencies As String() = {"ATS", "DEM", "ESP", "FIM", "FRF", _
"IEP", "ITL", "LUF", "NLG", "PTE"}
Dim conversionValues As Decimal() = {13.7603, 1.95583, 166.386, _
5.94573, 6.55957, 0.787564, _
1936.27, 40.3399, 2.20371, 200.482}
Do
Console.Write("Currencies : ")
Dim index As Integer
For index = 0 To count - 2
Console.Write(currencies(index) & " / ")
Next
Console.WriteLine(currencies(index))
Console.Write("Currency ? : ")
Dim currency As String = Console.ReadLine()
Dim lowerbound As Integer = 0
Dim upperbound As Integer = count - 1
Dim middle As Integer
Dim found As Boolean = False
Dim done As Boolean = False
Do Until found OrElse done
middle = (lowerbound + upperbound) \ 2
found = (currency = currencies(middle))
If Not found Then
done = (upperbound - lowerbound < 1)
If Not done Then
If currency > currencies(middle) Then
lowerbound = middle + 1
Else
upperbound = middle - 1
End If
End If
End If
Loop
If found Then
Console.Write("Amount " & currencies(middle) & " ? : ")
Dim amount As Decimal = Console.ReadLine()
Console.WriteLine("Conversion : " & amount & " " & _
currencies(middle) & " = " & _
amount / conversionValues(middle) & " EUR")
Else
Console.Write("Add Currency ( Y/N ) ? : ")
Dim addCurrency As Char = Console.ReadLine()
If addCurrency = "y"c OrElse addCurrency = "Y"c Then
Console.Write("Conversion Value " & currency & _
" ( = 1 EUR ) ? : ")
Dim conversionValue As Decimal = Console.ReadLine()
ReDim Preserve currencies(count)
ReDim Preserve conversionValues(count)
count += 1
index = count - 1
Do While (index - 1 >= 0) AndAlso _
(currencies(index - 1) > currency)
currencies(index) = currencies(index - 1)
conversionValues(index) = conversionValues(index - 1)
index -= 1
Loop
currencies(index) = currency
conversionValues(index) = conversionValue
End If
End If
Loop
End Sub
End ModuleDownload Visual Basic Broncode Bekijk deze Broncode in Visual C#
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. 
