Sortieralgorithmen: MergeSort

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

  • Kurze Implementierung des MergeSort-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 eine Liste von Integern in der Konsole auszugeben
    5. Sub print_list(ByRef liste As List(Of Integer))
    6. For Each element In liste
    7. Console.Write(element.ToString & " ")
    8. Next
    9. Console.WriteLine("-")
    10. End Sub
    11. 'Methode um ein liste mit Zufallswerten zu initialisieren
    12. Sub initialize_list(ByRef liste() As Integer)
    13. 'Zufallsgenerator initialisieren
    14. Dim r As New Random(System.DateTime.Now.Millisecond)
    15. 'Jedem Element der Schleife einen zufälligen Wert zuweisen
    16. For i As Integer = 0 To liste.Length - 1
    17. 'Zufallszahl zwischen 0 und 10.000 erzeugen und zuweisen
    18. liste(i) = r.Next(0, 10000)
    19. Next
    20. End Sub
    21. ' MergeSort implementation
    22. Sub MergeSort(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nUpper As Integer)
    23. ' Check for array size
    24. Dim szSwap As String
    25. If (nUpper - nLower) = 1 Then
    26. ' Swap strings if necessary
    27. If szArray(nLower).CompareTo(szArray(nUpper)) > 0 Then
    28. szSwap = szArray(nLower)
    29. szArray(nLower) = szArray(nUpper)
    30. szArray(nUpper) = szSwap
    31. End If
    32. ElseIf (nUpper - nLower) > 1 Then
    33. ' Sort each half and merge
    34. MergeSort(szArray, nLower, (nLower + nUpper) / 2)
    35. MergeSort(szArray, (nLower + nUpper) / 2 + 1, nUpper)
    36. Merge(szArray, nLower, (nLower + nUpper) / 2 + 1, nUpper)
    37. End If
    38. End Sub
    39. Sub Merge(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nMiddle As Integer, ByVal nUpper As Integer)
    40. Dim nIndex As Integer
    41. Dim szBuffer As New List(Of Integer)()
    42. Dim i, j As Integer
    43. i = nLower
    44. j = nMiddle
    45. While i < nMiddle And j <= nUpper
    46. If (szArray(i).CompareTo(szArray(j)) < 0) Then
    47. szBuffer.Add(szArray(i))
    48. i = i + 1
    49. Else
    50. szBuffer.Add(szArray(j))
    51. j = j + 1
    52. End If
    53. End While
    54. While i < nMiddle
    55. szBuffer.Add(szArray(i))
    56. i = i + 1
    57. End While
    58. While j <= nUpper
    59. szBuffer.Add(szArray(j))
    60. j = j + 1
    61. End While
    62. nIndex = 0
    63. For i = nLower To nUpper
    64. szArray(i) = szBuffer(nIndex)
    65. nIndex = nIndex + 1
    66. Next i
    67. End Sub
    68. Sub Main()
    69. Dim al As List(Of Integer) = New List(Of Integer)
    70. initialize_list(list_to_be_sorted)
    71. al.AddRange(list_to_be_sorted)
    72. print_list(list_to_be_sorted)
    73. MergeSort(al, 0, list_to_be_sorted.Length - 1)
    74. print_list(al)
    75. Console.ReadKey()
    76. End Sub
    77. 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.211 mal gelesen