Quellcode
- Module Module1
- 'liste mit 15 Elementen, welches später sortiert werden soll deklarieren
- Dim list_to_be_sorted(15) As Integer
- 'Hilfsroutine um eine Liste von Integern in der Konsole auszugeben
- Sub print_list(ByRef liste As List(Of Integer))
- For Each element In liste
- Console.Write(element.ToString & " ")
- Next
- Console.WriteLine("-")
- End Sub
- 'Methode um ein liste mit Zufallswerten zu initialisieren
- Sub initialize_list(ByRef liste() As Integer)
- 'Zufallsgenerator initialisieren
- Dim r As New Random(System.DateTime.Now.Millisecond)
- 'Jedem Element der Schleife einen zufälligen Wert zuweisen
- For i As Integer = 0 To liste.Length - 1
- 'Zufallszahl zwischen 0 und 10.000 erzeugen und zuweisen
- liste(i) = r.Next(0, 10000)
- Next
- End Sub
- ' MergeSort implementation
- Sub MergeSort(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nUpper As Integer)
- ' Check for array size
- Dim szSwap As String
- If (nUpper - nLower) = 1 Then
- ' Swap strings if necessary
- If szArray(nLower).CompareTo(szArray(nUpper)) > 0 Then
- szSwap = szArray(nLower)
- szArray(nLower) = szArray(nUpper)
- szArray(nUpper) = szSwap
- End If
- ElseIf (nUpper - nLower) > 1 Then
- ' Sort each half and merge
- MergeSort(szArray, nLower, (nLower + nUpper) / 2)
- MergeSort(szArray, (nLower + nUpper) / 2 + 1, nUpper)
- Merge(szArray, nLower, (nLower + nUpper) / 2 + 1, nUpper)
- End If
- End Sub
- Sub Merge(ByRef szArray As List(Of Integer), ByVal nLower As Integer, ByVal nMiddle As Integer, ByVal nUpper As Integer)
- Dim nIndex As Integer
- Dim szBuffer As New List(Of Integer)()
- Dim i, j As Integer
- i = nLower
- j = nMiddle
- While i < nMiddle And j <= nUpper
- If (szArray(i).CompareTo(szArray(j)) < 0) Then
- szBuffer.Add(szArray(i))
- i = i + 1
- Else
- szBuffer.Add(szArray(j))
- j = j + 1
- End If
- End While
- While i < nMiddle
- szBuffer.Add(szArray(i))
- i = i + 1
- End While
- While j <= nUpper
- szBuffer.Add(szArray(j))
- j = j + 1
- End While
- nIndex = 0
- For i = nLower To nUpper
- szArray(i) = szBuffer(nIndex)
- nIndex = nIndex + 1
- Next i
- End Sub
- Sub Main()
- Dim al As List(Of Integer) = New List(Of Integer)
- initialize_list(list_to_be_sorted)
- al.AddRange(list_to_be_sorted)
- print_list(list_to_be_sorted)
- MergeSort(al, 0, list_to_be_sorted.Length - 1)
- print_list(al)
- Console.ReadKey()
- End Sub
- End Module
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.
7.826 mal gelesen