Sortieralgorithmen: QuickSort

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Kurze Implementierung des QuickSort-Algorithmus in VB

    Quellcode

    1. Module Module1
    2. 'liste mit 15 Elementen, welches später sortiert werden soll deklarieren
    3. Dim list_to_be_sorted(15) As Integer
    4. 'Hilfsroutine um ein Integer-Array in der Konsole auszugeben
    5. Sub print_list(ByRef liste() As Integer)
    6. For Each element In liste
    7. Console.Write(element.ToString & " ")
    8. Next
    9. Console.WriteLine("-")
    10. End Sub
    11. 'Hilfsroutine um eine Liste von Integern in der Konsole auszugeben
    12. Sub print_list(ByRef liste As List(Of Integer))
    13. For Each element In liste
    14. Console.Write(element.ToString & " ")
    15. Next
    16. Console.WriteLine("-")
    17. End Sub
    18. 'Methode um ein liste mit Zufallswerten zu initialisieren
    19. Sub initialize_list(ByRef liste() As Integer)
    20. 'Zufallsgenerator initialisieren
    21. Dim r As New Random(System.DateTime.Now.Millisecond)
    22. 'Jedem Element der Schleife einen zufälligen Wert zuweisen
    23. For i As Integer = 0 To liste.Length - 1
    24. 'Zufallszahl zwischen 0 und 10.000 erzeugen und zuweisen
    25. liste(i) = r.Next(0, 10000)
    26. Next
    27. End Sub
    28. 'Hilfsmethode um zwei stellen im liste zu vertauschen
    29. Sub swap(ByRef x As Integer, ByRef y As Integer)
    30. Dim tmp As Integer
    31. tmp = x
    32. x = y
    33. y = tmp
    34. End Sub
    35. 'VB Implementierung des BubbleSort-Algorithmus wie er auf Wikipedia beschrieben ist: http://de.wikipedia.org/wiki/Bubblesort
    36. Sub bubblesort(ByRef liste() As Integer)
    37. Dim n As Integer = liste.Length
    38. Dim swapped As Boolean
    39. Do
    40. swapped = False
    41. For i As Integer = 0 To n - 2
    42. If (liste(i) > liste(i + 1)) Then
    43. swap(liste(i), liste(i + 1))
    44. swapped = True
    45. End If
    46. Next
    47. n = n - 1
    48. Loop While n > 1
    49. End Sub
    50. 'VB Implementierung des Insertionsort-Algorithmus wie er auf Wikipedia beschrieben ist: http://de.wikipedia.org/wiki/Insertionsort
    51. Sub insertionsort(ByRef liste() As Integer) '
    52. Dim val, j As Integer
    53. For i As Integer = 1 To liste.Length - 1
    54. val = liste(i)
    55. j = i
    56. While (j > 0 AndAlso liste(j - 1) > val)
    57. liste(j) = liste(j - 1)
    58. j = j - 1
    59. liste(j) = val
    60. End While
    61. Next
    62. End Sub
    63. ' MergeSort implementation
    64. Sub MergeSort(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nUpper As Integer)
    65. ' Check for array size
    66. Dim szSwap As String
    67. If (nUpper - nLower) = 1 Then
    68. ' Swap strings if necessary
    69. If szArray(nLower).CompareTo(szArray(nUpper)) > 0 Then
    70. szSwap = szArray(nLower)
    71. szArray(nLower) = szArray(nUpper)
    72. szArray(nUpper) = szSwap
    73. End If
    74. ElseIf (nUpper - nLower) > 1 Then
    75. ' Sort each half and merge
    76. MergeSort(szArray, nLower, (nLower + nUpper) / 2)
    77. MergeSort(szArray, (nLower + nUpper) / 2 + 1, nUpper)
    78. Merge(szArray, nLower, (nLower + nUpper) / 2 + 1, nUpper)
    79. End If
    80. End Sub
    81. Sub Merge(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nMiddle As Integer, ByVal nUpper As Integer)
    82. Dim nIndex As Integer
    83. Dim szBuffer As New List(Of Integer)()
    84. Dim i, j As Integer
    85. i = nLower
    86. j = nMiddle
    87. While i < nMiddle And j <= nUpper
    88. If (szArray(i).CompareTo(szArray(j)) < 0) Then
    89. szBuffer.Add(szArray(i))
    90. i = i + 1
    91. Else
    92. szBuffer.Add(szArray(j))
    93. j = j + 1
    94. End If
    95. End While
    96. While i < nMiddle
    97. szBuffer.Add(szArray(i))
    98. i = i + 1
    99. End While
    100. While j <= nUpper
    101. szBuffer.Add(szArray(j))
    102. j = j + 1
    103. End While
    104. nIndex = 0
    105. For i = nLower To nUpper
    106. szArray(i) = szBuffer(nIndex)
    107. nIndex = nIndex + 1
    108. Next i
    109. End Sub
    110. Public Function QuickSort(ByVal list As List(Of Integer)) As List(Of Integer)
    111. If list.Count < 1 Then Return list
    112. Dim Smaller As New List(Of Integer)
    113. Dim Larger As New List(Of Integer)
    114. Dim pt As Integer = 0
    115. QuickSort = New List(Of Integer)
    116. Dim pv As Integer = list(Int(Rnd() * list.Count))
    117. For i As Integer = 0 To list.Count - 1
    118. Select Case list(i)
    119. Case Is = pv
    120. pt += 1
    121. Case Is < pv
    122. Smaller.Add(list(i))
    123. Case Is > pv
    124. Larger.Add(list(i))
    125. End Select
    126. Next
    127. QuickSort.AddRange(QuickSort(Smaller))
    128. While pt > 0
    129. QuickSort.Add(pv)
    130. pt -= 1
    131. End While
    132. QuickSort.AddRange(QuickSort(Larger))
    133. End Function
    134. Sub Main()
    135. Dim al As List(Of Integer) = New List(Of Integer)
    136. initialize_list(list_to_be_sorted)
    137. al.AddRange(list_to_be_sorted)
    138. print_list(list_to_be_sorted)
    139. 'bubblesort(liste_to_be_sorted)
    140. 'insertionsort(liste_to_be_sorted)
    141. 'MergeSort(al, 0, list_to_be_sorted.Length - 1)
    142. al = QuickSort(al)
    143. print_list(al)
    144. 'print_list(list_to_be_sorted)
    145. Console.ReadKey()
    146. End Sub
    147. End Module
    Alles anzeigen


    Ich werde hier nicht auf die Spezifika des Algorithmus eingehen, da das sprachenunabhängig wäre und eher in die Rubrik Allgemein gehört. Es sei an dieser Stelle auf den Wikipedia-Artikel verwiesen, der eigentlich alles Nötige erklärt.

    6.444 mal gelesen