Bubblesort: Algorithmus zufriedenstellend, Implementierung fehlerhaft

Question

da mein letzter Thread, die Migration einer VB6-Application in VB.NET hier leider nicht zufriedenstellend bewältigt werden konnte, habe ich mich entschlossen, fundamentalere Aufgaben anzugehen. Nach Erstellung eines Struktogrammes zu Bubblesort dachte ich mir, die Implementierung wäre kein großes Problem mehr. Weit gefehlt. Das dynamische Einlesen/Auslesen von Zufallswerten bis zu einer fixen Grenze klappt zwar wunderbar, allerdings scheint -lt. Debugger- die Sortiermethode fehlerhaft. Woran liegt das bloß?????

vorab vielen Dank ob der Mühen. es bedarf hierzu sicherlich eines versierten Programmierers, um den Fehler zu finden, wobei ich hoffe, dass der Algorithmus zumindest nicht von vorne weg miserabel ist.

Public Class Form1
    Delegate Function compareF(ByVal x As Integer, ByVal y As Integer) As Boolean   ' Zeiger initialisieren
    Function aufsteigend(ByVal x As Integer, ByVal y As Integer) As Boolean                   
        If y < x Then aufsteigend = True                                                          
  End Function

    Function absteigend(ByVal x As Integer, ByVal y As Integer) As Boolean
        If y > x Then absteigend= True               
    End Function

    Sub bubblesort(ByVal compmethod As compareF, ByVal array() As Integer)
        Dim tmp As Integer
        For i As Integer = 0 To array.Length                               ' durchlaufe alle Werte bis Arrayende
            For j As Integer = i + 1 To array.Length - 1 'durchlaufe, abhängig von der Vorschleife bis zum
                If compmethod(array(i), array(j))=True  Then ' falls Zeigeraufruf nötig........
                    tmp = array(j)                                            'Algorithmusanweisung1
                    array(i)=tmp                                              'Algorithmusanweisung2
                  array(j)=array(i)                                           'Algorithmusanweisung3
                End If
            Next j
        Next i
    End Sub

    Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
        Dim rnd As New Random()
        Dim max As Integer = 20
        Dim array2(max - 1) As Integer
        ListBox1.Items.Clear()
        ListBox2.Items.Clear()
        ListBox3.Items.Clear()
        For i As Integer = 0 To max - 1
            array2(i) = rnd.Next(0, 200)                  ' Zufallswerte von 0-200(statisch) erzeugen
            ListBox1.Items.Add(array2(i).ToString)   ' in Listbox anzeigen und vorher in einen String konv.
        Next
        bubblesort(AddressOf aufsteigend, array2)   'Sortiermethode verwenden
        For i As Integer = 0 To max - 1
            ListBox2.Items.Add(array2(i).ToString)   ' sortierte Werte in String konvertieren und  ListBox ausg
        Next
        bubblesort(AddressOf absteigend, array2)
        For i As Integer = 0 To max - 1
            ListBox3.Items.Add(array2(i).ToString)
        Next
    End Sub

    Private Sub Button2_Click(sender As Object, e As EventArgs) Handles Button2.Click
        Me.Close()
    End Sub
End Class

Answer 1

Hi,
Deine BubbleSort-Implementation ist falsch. Ich würde es so implementieren:

  Sub bubblesort(ByVal compmethod As compareF, ByVal array() As Integer)
    Dim tmp As Integer
    For i As Integer = 0 To array.Length                               ' durchlaufe alle Werte bis Arrayende
      For j As Integer = i + 1 To array.Length - 1 'durchlaufe, abhängig von der Vorschleife bis zum 
        If compmethod(array(i), array(j)) = True Then ' falls Zeigeraufruf nötig........
          tmp = array(j)                                            'Algorithmusanweisung1
          array(j) = array(i)                                           'Algorithmusanweisung3
          array(i) = tmp                                              'Algorithmusanweisung2
        End If
      Next j
    Next i
  End Sub

--
Viele Grüsse
Peter Fleischer (MVP, Partner)
Meine Homepage mit Tipps und Tricks
Kommas richtig setzen! Leben retten!
Wir essen Opa.
Wir essen, Opa.

Answer 2

Oh jaaaa.

Keine Ahnung, wieso ich da die Zeilen vertauschte. Da war wohl bereits das Struktogramm fehlerhaft. Habe beide - gemäß deinen Angaben- korrigiert, und siehe dar, es funktioniert. Auch das dynamische Einlesen der Werte sowie der Arraygrenzen mittels Inputboxen funktioniert jetzt reibungslos.

Wie bist du da bloß draufgekommen?

Respekt & v.a. Danke bzw. Hut ab....!

Answer 3

Hallo,

trotzdem ist noch ein (kleiner) Fehler drin, der unnötiges Schleifen verursacht, richtiger wäre bei dem Aufbau:

 For i As Integer = 0 To array.Length - 2 

was zwei Durchläufe der äußeren Schleife vermeidet, die zwar sofort durch die innere beendet werden, aber überflüssig sind.

Für weitere Programmierversuche siehe BubbleSort (Wikipedia)

Für .NET sollte man den Einsatz von Func und von IComparable erwägen, womit ein generischer Ansatz ist, und eine kleine Programmieraufgabe dienen könnte.

Gruß Elmar