Visual Basic 2012 Voorbeelden
   

visual basic 2012 broncode voorbeelden

Blijf op de hoogte van de recente aanpassingen op vbvoorbeelden!

Microsoft Visual Studio 2012Microsoft Developers Network - Visual BasicMicrosoft .NET Framework

7.4. Sorteren van Arrays - Selection Sort

Print Email Deel op Twitter Deel op Facebook

Dit artikel is gepubliceerd op maandag 15 oktober 2012 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 Sort

We 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 2012 Broncode - Codevoorbeeld 119
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 Module
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 maandag 15 oktober 2012 op vbvoorbeelden, bezoek de website voor een recente versie van dit artikel of andere artikels.