Sortieralgorithmen

[autoit]

#include <Array.au3>
Dim $Feld[1000]
Dim $neuesFeld[1000]
For $i = 0 To 999 Step 1
$Feld[$i] = Random(1, 1000, 1)
Next
_ArrayDisplay($Feld)
$timer = TimerInit()
$neuesFeld = _InsertSort($Feld)
$zeit = TimerDiff($timer)
MsgBox(0,"Zeit","Der Algorithmus hat "&$zeit&" Millisekunden gebraucht!")
_ArrayDisplay($neuesFeld)

[/autoit] [autoit][/autoit] [autoit]

#cs
_BubbleSort (3539 msek bei 1000 Zahlen)
Es wird immer von vorne bis hinten durchsucht, ob das nächste Feld größer oder kleiner ist, als das untersuchte.
Wenn das nächste Feld kleiner ist, dann werden die Daten der beiden Felder ausgetauscht.
Der Array wird um eins weniger - fach untersucht, wie er Felder hat, also bei 100 Feldern 99 - mal.
Danach ist der Array sortiert
#ce
Func _BubbleSort($iArray)
If UBound($iArray,0) <> 1 Then
MsgBox(0,"ERROR","Sie haben keinen eindimensionalen Array angegeben")
Exit
EndIf
For $k = 0 To UBound($iArray,1)
For $i = 0 to (UBound($iArray,1)-2)
If $iArray[$i] > $iArray[$i + 1] Then
_ArraySwap($iArray[$i + 1], $iArray[$i])
EndIf
Next
Next
Return $iArray
EndFunc

[/autoit] [autoit][/autoit] [autoit]

#cs
_RippleSort (3498 msek bei 1000 Zahlen)
RippleSort ist fast identisch mit BubbleSort, jedoch ist die Abbruchbedingung anders.
Bei BubbleSort wird ein 100-Feld-Array 99-mal durgegangen, egal ob es noch etwas zum sortieren gibt.
Bei RippleSort wird ein Array solange durchsucht, bis es nichts mehr auszutauschen gibt.
#ce
Func _RippleSort($iArray)
If UBound($iArray,0) <> 1 Then
MsgBox(0,"ERROR","Sie haben keinen eindimensionalen Array angegeben")
Exit
EndIf
Do
$kontrolle = False
For $i = 0 to (UBound($iArray,1)-2)
If $iArray[$i] > $iArray[$i + 1] Then
_ArraySwap($iArray[$i + 1], $iArray[$i])
$kontrolle = True
EndIf
Next
Until $kontrolle == False
Return $iArray
EndFunc

#cs
_ShakerSort (2606 msek bei 1000 Zahlen)
Der Array wird zu Erst von vorne nach hinten durchsucht und ausgetauscht, wie bei BubbleSort, aber nur einmal.
Dann wird der Array von hinten nach vorne durchsucht und ausgetauscht.
Danach ist die größte Zahl hinten und die kleinste Zahl vorne.
Dadurch müssen das erste und letzte Feld nicht mehr untersucht werden.
Das wird wiederholt und dann sind die beiden größten Zahlen hinten und die beiden kleinsten Zahlen vorne.
Das wird solange wiederholt, bis sich die beiden Fronten in der Mitte treffen.
Dann ist der Array sortiert.
Ein ähnliches Verfahren namens Selectsort funktioniert genauso, jedoch wird immer von vorne nach hinten durchsucht und immer nur das letzte Feld abgeschnitten.
#ce
Func _ShakerSort($iArray)
If UBound($iArray,0) <> 1 Then
MsgBox(0,"ERROR","Sie haben keinen eindimensionalen Array angegeben")
Exit
EndIf
$links = 0
$rechts = UBound($iArray,1)-1
Do
$iArray = _ShakerLinks($iArray,$links,$rechts)
$links += 1
$iArray = _ShakerRechts($iArray,$links,$rechts)
$rechts -= 1
Until $links > $rechts
Return $iArray
EndFunc
Func _ShakerLinks($lArray,$l,$r)
For $i=$l To $r-1 Step 1
If $lArray[$i] > $lArray[$i + 1] Then
_ArraySwap($lArray[$i + 1], $lArray[$i])
EndIf
Next
Return $lArray
EndFunc
Func _ShakerRechts($rArray,$l,$r)
For $i = $r-1 To $l Step -1
If $rArray[$i] < $rArray[$i - 1] Then
_ArraySwap($rArray[$i - 1], $rArray[$i])
EndIf
Next
Return $rArray
EndFunc

[/autoit] [autoit][/autoit] [autoit]

#cs
_InsertSort (2572 msek bei 1000 Zahlen)
es wird von vorne bis hinten durchgeguckt, ob die aktuell untersuchte Zahl weiter vorne einsortiert werden kann.
Wenn also $i zum Beispiel bei 5 ist, dann wird geprüft, ob sich die zahl zwischen 3 und 4, 2 und 3, 1 und 2, oder 0 und 1 einsortieren lässt.
#ce
Func _InsertSort($iArray)
For $i = 0 To (UBound($iArray,1)-2) Step 1
For $j = $i To 0 Step -1
If $iArray[$j] > $iArray[$j+1] Then
_ArraySwap($iArray[$j],$iArray[$j+1])
EndIf
Next
Next
Return $iArray
EndFunc
#cs
Anschaulich:
_BubbleSort 3539 msek
_RippleSort 3498 msek
_ShakerSort 2606 msek
_InsertSort 2572 msek
#ce

[/autoit]