Die üblichen Sortieralgorithmen beruhen auf direkten Größenvergleichen zwischen zwei Elementen.
Mathematisch kann man beweisen, dass man hiermit jedoch auf ein Laufzeitverhalten von n*log(n) beschränkt ist.
Auch _ArraySort unterliegt dieser Beschränkung. Dennoch ist sie durch die (optionale) Verwendung des Dual-Pivot-Quicksorts und der Verwendung von Insertionsort für kleine Teilarrays sehr nahe an einem möglichen Optimum.
Dennoch stellt sich die Frage: Gibt es denn trotzdem Alternativen?: Jein
Ein Algorithmus welcher nicht auf Größenvergleichen beruht ist Radix-Sort.
Sein Grundansatz ist ein anderer: Alle Werte werden stellenweise betrachtet. Man beginnt mit der ersten Stelle und schmeißt alle Zahlen entsprechend ihrem Stellenwert in einen bestimmten Topf. Hat man das gemacht fügt man alle Töpfe in der Reihe ihres Stellenwertes wieder aneinander.
Dann wiederholt man das Spielchen für die restlichen Stellen.
Am Ende liegen die Werte sortiert vor. (Genauere Beschreibungen siehe google)
Nun die Frage: Warum wurde dieses Verfahren bisher noch nicht in AutoIt implementiert?
Das liegt einerseits an der Beschränkung der zu sortierenden Datentypen.
Der Sortierschlüssel der Werte muss aus "Zeichen eines endlichen Alphabets" bestehen (Zitat Wikipedia ;-).
Vorzeichenlose Integer sind ein Beispiel hierfür, oder auch Objekte mit einem UInt als Sortierungsschlüssel.
Auf der anderen Seite benötigt man schnelle dynamische Datenstrukturen für die Zwischenspeicherung.
AutoIt-Arrays waren dafür schlicht nicht geeignet.
Mit dem Map-Datentyp der aktuellen Betas steht nun aber eine derartige Struktur zur Verfügung.
Das brachte mich dazu den RadixSort nun auch einmal in Autoit zu implementieren:
RadixSort in AutoIt (benötigt AutoIt-Version > 3.3.13.6)
#include <Array.au3>
[/autoit] [autoit][/autoit] [autoit]; ################### Random-Array erstellen ######################
Global Const $nEl = 1e3 ; Anzahl Elemente
Global Const $dMaxEl = 1e5 - 1 ; Wertebereich
Global $ARnd[$nEl]
For $i = 0 To $nEl - 1
$ARnd[$i] = Random(0, $dMaxEl, 1)
Next
_ArrayDisplay($ARnd, "unsortiert")
; -----------------------------------------------------------------
$t = $ARnd
$iT = TimerInit()
_ArraySort($t)
ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArraySort", TimerDiff($iT)))
$t = $ARnd
$iT = TimerInit()
_ArrayRadixSortLSD($t, __dRadixUInt)
ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortLSD", TimerDiff($iT)))
$t = $ARnd
$iT = TimerInit()
_ArrayRadixSortMSD_Stable($t, __dRadixUInt)
ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortMSD_Stable", TimerDiff($iT)))
$t = $ARnd
$iT = TimerInit()
_ArrayRadixSortMSD($t, __dRadixUInt)
ConsoleWrite(StringFormat("% 30s: %8.3f ms\n", "_ArrayRadixSortMSD", TimerDiff($iT)))
; #FUNCTION# ======================================================================================
; Name ..........: _ArrayRadixSortLSD
; Description ...: sort an array with radix-sort (LSD=Least significant digit)
; Syntax ........: _ArrayRadixSort(ByRef $A, Const $F, [$N = Default])
; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
; Return values .: Success: True - array is sorted now
; Failure: False
; @error = 1: $A is'nt an array
; 2: invalid value for $F
; Author ........: AspirinJunkie
; Related .......: AutoIt-version > 3.3.13.6
; Remarks .......: see Wikipedia for an explanation for which data you can use it
; =================================================================================================
Func _ArrayRadixSortLSD(ByRef $A, Const $F, $N = Default)
Local $i, $t, $nn, $u, $rn = 0
Local Const $iMax = UBound($A) - 1
; error-handling:
If Not IsArray($A) Then Return SetError(1, 0, False)
If Not IsFunc($F) Then Return SetError(2, 0, False)
; evaluate the maximum number of digits:
If $N = Default Then
$N = 1
For $i = 0 To $iMax
If $N < $F($A[$i]) Then $N = $F($A[$i])
Next
EndIf
; get the digit order definition:
Local Const $O = $F()
; create the bucket holders:
Local $m[], $r[] ; $m = the temporary bucket-holder, $r = the already sorted bucket holder
; sorting!:
For $d = 1 To $N
; create (and empty) buckets:
For $i In $O
Dim $t[]
$m[String($i)] = $t
Dim $t[]
$r[String($i)] = $t
Next
; sort into the buckets related to the current digit:
For $i = $rn To $iMax
$t = $A[$i]
$u = $F($t, $d)
If @extended Then
MapAppend($r[$u], $t)
Else
MapAppend($m[$u], $t)
EndIf
Next
; convert back to array (merge the buckets to the array):
; at first add the already sorted elements:
For $k In $O
$t = $r[String($k)]
$nn = UBound($t) - 1
For $e = 0 To $nn
$A[$rn] = $t[$e]
$rn += 1
Next
Next
; now add the leftover elements:
$i = $rn
For $k In $O
$t = $m[String($k)]
$nn = UBound($t) - 1
For $e = 0 To $nn
$A[$i] = $t[$e]
$i += 1
Next
Next
Next
Return True
EndFunc ;==>_ArrayRadixSortLSD
; #FUNCTION# ======================================================================================
; Name ..........: _ArrayRadixSortMSD
; Description ...: sort an array with radix-sort (MSD=Most significant digit)
; this implementation is stable(maintain the relative order of records with equal keys) but not in-place
; Syntax ........: _ArrayRadixSortMSD(ByRef $A, Const $F, [$N = Default, [$iMin = 0, [$iMax = UBound($A) - 1, {$d = Default, {Const $b_First = True}}]]])
; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
; $iMin - start index for the array-range which should be sorted
; $iMax - end index for the array-range which should be sorted
; $d - Don't touch! - internal parameter which defines the actual radix
; $b_First - Don't touch! - internal parameter for recognize if actual function call is the begin of the recursion
; Return values .: Success: True - array is sorted now
; Failure: False
; @error = 1: $A isn't an array
; 2: invalid value for $F
; 3: $A isn't a 1D-Array
; 4: wrong value for $iMin
; 5: wrong value for $iMax
; 6: wrong combination of $iMin and $iMax
; Author ........: AspirinJunkie
; Related .......: AutoIt-version > 3.3.13.6
; Remarks .......: see Wikipedia for an explanation for which data you can use it
; =================================================================================================
Func _ArrayRadixSortMSD(ByRef $A, ByRef Const $F, $N = Default, $iMin = 0, $iMax = UBound($A) - 1, $d = Default, Const $b_First = True)
Local $count[], $pos, $j, $c, $u, $t
Local Const $dLen = $iMax - $iMin ; Array-Size
If $b_First Then
; error-handling:
If Not IsArray($A) Then Return SetError(1, 0, False) ; no array
If Not IsFunc($F) Then Return SetError(2, 0, False) ; no function
If UBound($A, 0) <> 1 Then Return SetError(3, 0, 0) ; no 1D-array
If Not IsInt($iMin) Or $iMin < 0 Then Return SetError(4, $iMin, False) ; wrong value in $iMin
If Not IsInt($iMax) Or $iMax > UBound($A) - 1 Then Return SetError(5, $iMin, False) ; wrong value in $iMax
If $iMin > $iMax Then Return SetError(6, $iMax - $iMin, False) ; wrong combination of $iMin and $iMax
; evaluate the maximum number of digits:
If $N = Default Then
$N = 1
For $i = 0 To $iMax
If $N < $F($A[$i]) Then $N = $F($A[$i])
Next
EndIf
$d = $N
EndIf
; get the digit order definition:
Local Const $O = $F()
; reset the maps for the digit counter
For $i In $O
$count[String($i)] = 0
Next
; count for every digit how much elements are in it:
For $i = $iMin To $iMax
$count[$F($A[$i], $d)] += 1
Next
; calculate the positions of digit-area start in the result-array (=partial sum):
$pos = $count
For $i = 1 To UBound($O) - 1
$pos[String($O[$i])] = $count[String($O[$i])] + $pos[String($O[$i - 1])]
Next
; reorder items:
$i = 0
Do
While 1
$u = $F($A[$iMin + $i], $d)
$pos[$u] -= 1
$j = $pos[$u]
If $j <= $i Then ExitLoop
; swap A[iMin + i] <-> A[iMin + j]
$c = $A[$iMin + $i]
$A[$iMin + $i] = $A[$iMin + $j]
$A[$iMin + $j] = $c
WEnd
$i += $count[$F($A[$iMin + $i], $d)]
Until $i >= $dLen
If $d < 2 Then Return True
[/autoit] [autoit][/autoit] [autoit]; recursivly sort digit-related subarrays:
$u = $iMin
For $i In $O
$c = $count[String($i)]
If $c > 1 Then _ArrayRadixSortMSD($A, $F, $N, $u, $u + $c - 1, $d - 1, False)
$u += $c
Next
Return True
EndFunc ;==>_ArrayRadixSortMSD2
; #FUNCTION# ======================================================================================
; Name ..........: _ArrayRadixSortMSD_Stable
; Description ...: sort an array with radix-sort (MSD=Most significant digit)
; this implementation is stable(maintain the relative order of records with equal keys) but not in-place
; Syntax ........: _ArrayRadixSortMSD_Stable(ByRef $A, Const $F, [$N = Default, [$iMin = 0, [$iMax = UBound($A) - 1, {$d = Default, {Const $b_First = True}}]]])
; Parameters ....: $A - the array which should be sorted (by reference means: direct manipulating of the array - no copy)
; $F - a function which defines the datatype/digit-system of the array-values (see an example for deeper details)
; $N - the maximum number of value-digits (if Default then evaluate this value from array - slower)
; $iMin - start index for the array-range which should be sorted
; $iMax - end index for the array-range which should be sorted
; $d - Don't touch! - internal parameter which defines the actual radix
; $b_First - Don't touch! - internal parameter for recognize if actual function call is the begin of the recursion
; Return values .: Success: True - array is sorted now
; Failure: False
; @error = 1: $A isn't an array
; 2: invalid value for $F
; 3: $A isn't a 1D-Array
; 4: wrong value for $iMin
; 5: wrong value for $iMax
; 6: wrong combination of $iMin and $iMax
; Author ........: AspirinJunkie
; Related .......: AutoIt-version > 3.3.13.6
; Remarks .......: see Wikipedia for an explanation for which data you can use it
; =================================================================================================
Func _ArrayRadixSortMSD_Stable(ByRef $A, ByRef Const $F, $N = Default, $iMin = 0, $iMax = UBound($A) - 1, $d = Default, Const $b_First = True)
Local Static $aAux[0]
Local $count[], $j, $iOld, $c, $p, $u, $t
Local Const $dLen = $iMax - $iMin ; Array-Size
; error-handling:
If Not IsArray($A) Then Return SetError(1, 0, False)
If Not IsFunc($F) Then Return SetError(2, 0, False)
If $b_First Then
; error-handling:
If Not IsArray($A) Then Return SetError(1, 0, False) ; no array
If Not IsFunc($F) Then Return SetError(2, 0, False) ; no function
If UBound($A, 0) <> 1 Then Return SetError(3, 0, 0) ; no 1D-array
If Not IsInt($iMin) Or $iMin < 0 Then Return SetError(4, $iMin, False) ; wrong value in $iMin
If Not IsInt($iMax) Or $iMax > UBound($A) - 1 Then Return SetError(5, $iMin, False) ; wrong value in $iMax
If $iMin > $iMax Then Return SetError(6, $iMax - $iMin, False) ; wrong combination of $iMin and $iMax
ReDim $aAux[UBound($A)]
; evaluate the maximum number of digits:
If $N = Default Then
$N = 1
For $i = 0 To $iMax
If $N < $F($A[$i]) Then $N = $F($A[$i])
Next
EndIf
$d = $N
EndIf
; get the digit order definition:
Local Const $O = $F()
; reset the maps for the digit counter and start-positions
For $i In $O
$count[String($i)] = 0
Next
$pos = $count
; count for every digit how much elements are in it:
For $i = $iMin To $iMax
$count[$F($A[$i], $d)] += 1
Next
; calculate the positions of digit-area start in the result-array (=partial sum):
For $i = 1 To UBound($O) - 1
$pos[String($O[$i])] = $count[String($O[$i - 1])] + $pos[String($O[$i - 1])]
Next
; iterate through the array and put the elements in their digit-related part of the result-array:
For $i = $iMin To $iMax
$t = $A[$i]
$u = $F($t, $d)
$aAux[$pos[$u]] = $t
$pos[$u] += 1
Next
; transfer changes to input array
For $i = $iMin To $iMax
$A[$i] = $aAux[$i - $iMin]
Next
; sort the digit-related-subarrays recursively
If $d > 0 Then
For $i In $O
$c = $count[String($O[$i])]
$p = $pos[String($O[$i])] + $iMin - $c
If $c > 1 Then _ArrayRadixSortMSD_Stable($A, $F, $N, $p, $p + $c - 1, $d - 1, False)
Next
EndIf
If $b_First Then ReDim $aAux[0]
Return True
EndFunc ;==>_ArrayRadixSortMSD_Stable
; #FUNCTION# ======================================================================================
; Name ..........: __dRadixUInt
; Description ...: return the nth digit of an value / return the number of digits of a value / return the digit order definition array
; Syntax ........: __dRadixUInt([Const $v = Default, [Const $N = Default]])
; Parameters ....: $v - the value which should be analysed
; $N - the digit position which should be extracted from the value
; Return values .: this is an multi-functional function. It's return value depends on the parameter-combination:
; $v and $N is setted - return the nth digit of $v
; only $v is setted - return the number of digits of $v
; nothing is setted - return the digit order definition array
; @extended = 1 - if $N = the last digit (help speed up RadixSort)
; Author ........: AspirinJunkie
; Related .......: _ArrayRadixSort()
; =================================================================================================
Func __dRadixUInt(Const $v = Default, Const $N = Default)
Local Static $aRet[10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Local Const $d = StringLen($v)
If $v = Default Then Return $aRet ; return digit order definition
If $N = Default Then Return $v = 0 ? 0 : $d ; return the number of digits of $value
If $N = $d Then Return SetExtended(1, StringLeft($v, 1))
Return $N > $d ? "0" : StringLeft(StringRight($v, $N), 1) ; return the nth digit of $value
EndFunc ;==>__dRadixUInt
; #FUNCTION# ======================================================================================
; Name ..........: __dRadixString
; Description ...: return the nth digit of an String / return the number of digits of a value / return the digit order definition array
; Syntax ........: __dRadixString([Const $v = Default, [Const $N = Default]])
; Parameters ....: $v - the value which should be analysed
; $N - the digit position which should be extracted from the value
; Return values .: this is an multi-functional function. It's return value depends on the parameter-combination:
; $v and $N is setted - return the nth digit of $v
; only $v is setted - return the number of digits of $v
; nothing is setted - return the digit order definition array
; @extended = 1 - if $N = the last digit (help speed up RadixSort)
; Author ........: AspirinJunkie
; Related .......: _ArrayRadixSort()
; =================================================================================================
Func __dRadixString(Const $v = Default, Const $N = Default)
Local Static $aRet[26] = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]
Local Const $d = StringLen($v)
If $v = Default Then Return $aRet ; return digit order definition
If $N = Default Then Return $v = "" ? 0 : $d ; return the number of digits of $value
If $N = $d Then Return SetExtended(1, StringLeft($v, 1))
Return $N > $d ? "0" : StringLeft(StringRight($v, $N), 1) ; return the nth digit of $value
EndFunc ;==>__dRadixString