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
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):
Selection Sort
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:
Quick Sort
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
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
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):
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.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
Selection Sort
VB.NET-Quellcode
- 'für das aktuelle Element entdeckt wurde (Zahl davor kleiner, Zahl danach größer, wird das Element in diese verschoben.
- Function SelectionSort(ByVal a As Integer())
- Dim lowest As Integer
- Dim temp As Integer
- For i = 0 To UBound(a) - 1
- lowest = i
- For j = i To UBound(a)
- If a(j) < a(lowest) Then
- lowest = j
- End If
- Next j
- temp = a(i)
- a(i) = a(lowest)
- a(lowest) = temp
- Next i
- Return a
- 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
- Public Function QuickSort(ByVal vSort As Integer(), ByVal start As Integer, ByVal ende As Integer)
- Dim h As Integer
- Dim x As Integer
- Dim i As Integer = start
- Dim j As Integer = ende
- x = vSort((start + ende) / 2)
- Do
- While (vSort(i) < x)
- i = i + 1
- End While
- While (vSort(j) > x)
- j = j - 1
- End While
- If (i <= j) Then
- h = vSort(i)
- vSort(i) = vSort(j)
- vSort(j) = h
- i = i + 1
- j = j - 1
- End If
- Loop Until (i > j)
- If (start < j) Then QuickSort(vSort, start, j)
- If (i < ende) Then QuickSort(vSort, i, ende)
- Return vSort
- 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