Probleme mit Mergesort

  • VB.NET

Es gibt 3 Antworten in diesem Thema. Der letzte Beitrag () ist von Niko Ortner.

    Probleme mit Mergesort

    Hallo zusammen,

    ich habe versucht Mergesort in Visual Basic zu programmieren, habe den Algorithmus soweit verstanden, nur scheitere ich an der Umsetzung in VB. (Programmiere noch nicht all zu lange :/ )
    Der rekursive Teil, in dem der Array bis zur Listenlänge von 1 aufgeteilt wird, funktioniert. Das Problem besteht in dem "merging" der einzelnen kleinen Listen..als Ausgabe erhalte ich ausschließlich Nullen.

    Mein Code sieht so aus:


    Visual Basic-Quellcode

    1. ​
    2. Public Class Form1
    3. Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
    4. Dim testA(8), output(8) As Integer
    6. testA(1) = 2
    7. testA(2) = 3
    8. testA(3) = 4
    9. testA(4) = 5 'Testarray
    10. testA(5) = 1
    11. testA(6) = 6
    12. testA(7) = 7
    13. testA(8) = 8
    15. output = Mergesort(testA)
    17. For i = 1 To testA.Length - 1
    18. ListBox1.Items.Add(output(i)) 'Ausgabe in Listbox
    19. Next
    21. End Sub
    23. Private Function Mergesort(ByVal m As Array) As Integer()
    25. Dim leftA((m.Length - 1) / 2), rightA((m.Length - 1) / 2) As Integer
    27. If m.Length - 1 <= 1 Then
    28. Return m 'Abbruch bei Listenlänge von 1
    29. Else
    30. For i = 1 To (m.Length - 1) / 2
    31. leftA(i) = m(i) 'Aufteilung des Arrays in linke (& rechte Liste)
    32. Next
    33. For i = (m.Length - 1) / 2 + 1 To m.Length - 1 'Aufteilung des Arrays in linke (& rechte Liste)
    34. rightA(i - ((m.Length - 1) / 2)) = m(i)
    35. Next
    37. leftA = Mergesort(leftA) 'Selbstaufruf bis Arraylänge = 1
    38. rightA = Mergesort(rightA)
    40. Return merge(leftA, rightA)
    42. End If
    43. End Function
    45. Private Function merge(ByVal x As Array, ByVal y As Array) As Integer()
    46. Dim leftA(x.Length - 1) As Integer
    47. Dim rightA(y.Length - 1) As Integer
    48. Dim sortedA(8) As Integer
    49. Dim pos As Integer = 1
    51. leftA = x
    52. rightA = y
    54. While leftA.Length - 1 > 0 And rightA.Length - 1 > 0 'Bei Arraylänge ab 1
    55. If leftA(1) <= rightA(1) Then 'wird sortiert (per "merging"),
    56. sortedA(pos) = leftA(1) 'der kleinere Wert in das neue Array hinzugefügt
    58. Dim tempArray(leftA.Length - 2) As Integer
    59. For i = 1 To leftA.Length - 2 'und aus dem vorherigen Array gelöscht und dieser wird "aufgeschoben"
    60. tempArray(i) = leftA(i + 1)
    61. Next
    62. ReDim Preserve leftA(leftA.Length - 2)
    63. leftA = tempArray
    64. Else
    65. sortedA(pos) = rightA(1) 'Else für den Fall, dass die andere Zahl kleiner ist
    66. End If
    67. pos += 1 'pos nimmt Werte an, die außerhalb der Arraylänge liegen, wieso? :s
    68. End While
    70. If leftA.Length - 1 > 0 Then '|
    71. For i = 1 To leftA.Length - 1 '|
    72. sortedA(pos) = leftA(i) '|
    73. Next '| Rest wird dem neuen Array hinzugefügt
    74. ElseIf rightA.Length - 1 > 0 Then '|
    75. For i = 1 To rightA.Length - 1 '|
    76. sortedA(pos) = rightA(i) '|
    77. Next
    78. End If
    79. pos += 1
    81. Return sortedA
    82. End Function
    84. End Class


    Über Hilfe jeglicher Art wäre ich sehr glücklich. :)
    Levyce

    Du machst mehere Sachen falsch. Zum beispiel startet ein array in Visual Basic mit 0, nicht mit 1. Bei der Array-Deklaration wird auch nicht die Größe, sondern der maximale Index (= Größe - 1) angegeben. Ferner kann man viele deiner Berechnungen vereinfachen. Die Merge methode soll eigentlich nur auf einem einzigen ausgabe-array arbeiten. siehe Code unten:

    VB.NET-Quellcode

    1. Public Class Form1
    2. Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
    3. Dim testA(8), output(8) As Integer
    4. testA(0) = 54
    5. testA(1) = 22
    6. testA(2) = 31
    7. testA(3) = 4
    8. testA(4) = 5 'Testarray
    9. testA(5) = 1
    10. testA(6) = 6
    11. testA(7) = 7
    12. testA(8) = 8
    13. output = Mergesort(testA)
    14. For i = 0 To testA.Length - 1
    15. ListBox1.Items.Add(output(i)) 'Ausgabe in Listbox
    16. Next
    17. End Sub
    18. Private Function Mergesort(ByVal m As Array) As Integer()
    19. Dim leftA((m.Length / 2.0) - 1) As Integer
    20. Dim rightA(m.Length - leftA.Length - 1) As Integer
    21. If m.Length <= 1 Then
    22. Return m 'Abbruch bei Listenlänge von 1 oder 0
    23. Else
    24. For i = 0 To leftA.Length - 1
    25. leftA(i) = m(i) 'Aufteilung des Arrays in linke (& rechte Liste)
    26. Next
    27. For i = 0 To rightA.Length - 1 'Aufteilung des Arrays in linke (& rechte Liste)
    28. rightA(i) = m(i + leftA.Length)
    29. Next
    30. leftA = Mergesort(leftA) 'Selbstaufruf bis Arraylänge = 1
    31. rightA = Mergesort(rightA)
    32. Return merge(leftA, rightA)
    33. End If
    34. End Function
    35. Private Function merge(ByVal x As Array, ByVal y As Array) As Integer()
    36. Dim result(x.Length + y.Length - 1) As Integer
    37. Dim i As Integer = 0
    38. Dim x_i As Integer = 0
    39. Dim y_i As Integer = 0
    41. While x_i < x.Length AndAlso y_i < y.Length
    42. If x(x_i) <= y(y_i) Then
    43. result(i) = x(x_i)
    44. x_i += 1
    45. Else
    46. result(i) = y(y_i)
    47. y_i += 1
    48. End If
    49. i += 1
    50. End While
    52. While x_i < x.Length
    53. result(i) = x(x_i)
    54. x_i += 1
    55. i += 1
    56. End While
    58. While y_i < y.Length
    59. result(i) = y(y_i)
    60. y_i += 1
    61. i += 1
    62. End While
    64. Return result
    65. End Function
    66. End Class

    @Levyce
    Ich würde Dir empfehlen, Option Strict auf On zu stellen.
    Visual Studio - Empfohlene Einstellungen
    Du übergibst überall die untypisierten Arrays als Parameter (gibst aber passenderweise die typisierten Arrays zurück).
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

Facebook
Telefonspende