Sortierung von Zahlen

    • Allgemein

    Es gibt 1 Antwort in diesem Thema. Der letzte Beitrag () ist von Memo.

      Sortierung von Zahlen

      Hallo zusammen,
      Sortierung von Zahlen - Klingt Einfach, ist es auch. ABER: Es gibt sehr viele Möglichkeiten, wie man das macht. Ein paar Methoden sind schnell, aber kompliziert, ein paar sind sehr einfach aber langsam. Ich will hier mal 3 Methoden zeigen und erklären: BubbleSort, InsertSort und QuickSort.


      BubbleSort

      VB.NET-Quellcode

      1. Function BubbleSort(ByVal a As Integer())
      2. Dim temp As Integer
      3. For i = 0 To UBound(a) - 1
      4. For j = 0 To UBound(a) - i - 1
      5. If a(j) > a(j + 1) Then
      6. temp = a(j)
      7. a(j) = a(j + 1)
      8. a(j + 1) = temp
      9. End If
      10. Next j
      11. Next i
      12. Return a
      13. End Function

      Es wird der Reihe nach jedes Element durchgegangen. Wenn es kleiner als das vorherige ist, wird es vor dieses geschoben. Beispiel (fett gedruckte Zahlen werden getauscht):
      Ausgangslage:
      19 12 20
      Erster Durchlauf
      19 12 20 → 12 19 20
      12 19 20→ 12 19 20
      Zweiter Durchlauf
      12 19 20 → 12 19 20
      12 19 20→ 12 19 20
      Diese Methode ist sehr ineffizient, dafür ist sie am einfachsten zu implementieren. Der Name “BubbleSort” kommt von der Vorstellung, dass die großen Zahlen wie Luftblasen im Wasser an das Ende der Reihe steigen.


      Selection Sort

      VB.NET-Quellcode

      1. 'für das aktuelle Element entdeckt wurde (Zahl davor kleiner, Zahl danach größer, wird das Element in diese verschoben.
      2. Function SelectionSort(ByVal a As Integer())
      3. Dim lowest As Integer
      4. Dim temp As Integer
      5. For i = 0 To UBound(a) - 1
      6. lowest = i
      7. For j = i To UBound(a)
      8. If a(j) < a(lowest) Then
      9. lowest = j
      10. End If
      11. Next j
      12. temp = a(i)
      13. a(i) = a(lowest)
      14. a(lowest) = temp
      15. Next i
      16. Return a
      17. End Function

      Auch hier wird der Reihe nach jedes Element (=Zahl) durchgegangen. Dann werden alle Zahlen vor der aktuellen Zahl durchgegangen. Sobald die passende Lücke
      für das aktuelle Element entdeckt wurde (Zahl danach größer) wird das Element in diese verschoben.
      Beispiel:
      19 12 20 → 12 19 20
      12 19 20 → 12 19 20


      Quick Sort

      VB.NET-Quellcode

      1. Public Function QuickSort(ByVal vSort As Integer(), ByVal start As Integer, ByVal ende As Integer)
      3. Dim h As Integer
      4. Dim x As Integer
      6. Dim i As Integer = start
      7. Dim j As Integer = ende
      8. x = vSort((start + ende) / 2)
      10. Do
      11. While (vSort(i) < x)
      12. i = i + 1
      13. End While
      14. While (vSort(j) > x)
      15. j = j - 1
      16. End While
      17. If (i <= j) Then
      18. h = vSort(i)
      19. vSort(i) = vSort(j)
      20. vSort(j) = h
      21. i = i + 1
      22. j = j - 1
      23. End If
      24. Loop Until (i > j)
      26. If (start < j) Then QuickSort(vSort, start, j)
      27. If (i < ende) Then QuickSort(vSort, i, ende)
      28. Return vSort
      29. End Function


      Diese Methode ist unter den hier vorgestellten die schnellste. Diese Methode unterteilt unseren Array zuerst in zwei Hälften. In der ersten Hälfte sind die Zahlen, die kleiner als die Zahl in der Mitte sind, in der zweiten die größeren. Diese zwei Hälften werden wieder nach dem gleichen Prinzip in zwei Hälften geteilt, in dem sich die Methode selber aufruft. Dieses “sich selber aufrufen” nennt man in der Informatik rekursiv. Es wird also immer weiter in Hälften geteilt, solang, bis eine solche “Hälfte von einer Hälfte von...” nur noch aus einer einzigen Zahl besteht. Beispiel:


      Quellen:
      springer.com/computer/theoreti…ce/book/978-3-540-76393-2
      vbarchiv.net/tipps/tipp_372-quicksort-in-vb.html
      it-academy.cc/article/1360/Der+BubbleSortAlgorithmus.html

    Facebook
    Telefonspende