Visual Basic 2010 Sorteren van Arrays

home links
visual basic 2010 broncode voorbeelden

7.6. Sorteren van Arrays - Insertion Sort

Dit artikel is gepubliceerd op zondag 31 juli 2011 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 2010 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 Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application 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 Sort

De meeste programmeertalen beschikken reeds over voorgedefinieerde functionaliteiten voor het sorteren van tabellen. Hier is dit niet anders.

Visual Basic 2010 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 Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application 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.

boven boven

7.6.2. Performantie van Sorteermethoden

Als 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.

boven boven

7.6.3. Oefening

Opgave :

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 2010 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
            ' ... binary search for currency in currencies ...
            '
            If found Then
                ' ... conversion of certain amount ...
            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()
                    '
                    ' ... insertion currency in currencies ...
                    ' ... conversionValue in conversionValues ...
                End If
            End If
        Loop
    End Sub
End Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Console Application 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 2010 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 Module

Download Visual Basic 2010 Broncode Download Visual C# Sourcecode

Dit artikel is gepubliceerd op zondag 31 juli 2011 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.

hoofdstuk	6. Constanten 7. Arrays 8. Procedures en Functies
onderwerp	7.5. Sorteren van Arrays - Bubble Sort 7.6. Sorteren van Arrays - Insertion Sort 7.7. Meerdimensionale Arrays
broncode	Download Sorteren-van-Arrays-Insertion-Sort.vb of Sorteren-van-Arrays-Insertion-Sort.cs
datum	laatst gewijzigd op donderdag 20 november 2008, laatst gepubliceerd op zondag 31 juli 2011

visual basic 2010 broncode voorbeelden

7.6. Sorteren van Arrays - Insertion Sort

7.6.1. Voorgedefinieerde Sorteermethoden - Quick Sort

7.6.2. Performantie van Sorteermethoden

7.6.3. Oefening

7.6.1. Voorgedefinieerde Sorteermethoden - Quick Sort

7.6.2. Performantie van Sorteermethoden

7.6.3. Oefening