Updates:
v1.0 available - now it's using Quicksort
Lexikos recently released an update for AK v2 which good me into the mood to play around with AHK v2 a bit.
One thing I see a lot in other languages is a sort function that looks and works similar to this:
Code: Select all
Arr.sort( compareFunction := defaultSortFunction )
Sort( arr, compareFunction := defaultSortFunction )We do have a sort function in AHK. But we do not talk about this one.
Anyways with this I have started to replicate this function:
Code: Select all
/* written by nnnik
https://autohotkey.com/boards/viewtopic.php?f=6&t=46260
v1.0.0
Changelog:
v0.1.0 Implemented an example using insertion sort
v1.0.0 It now uses quick sort
*/
sort( arr, compareFn := "" ) {
if !compareFn
compareFn := func( "standardCompare" )
layer := 0
quickSort( arr.MinIndex(), arr.MaxIndex() )
return arr
quickSort( firstIndex, lastIndex ) {
if lastIndex-firstIndex < 100
return insertSort( firstIndex, lastIndex )
leftIndex := firstIndex
rightIndex := lastIndex
pivotIndex := floor( ( rightIndex - leftIndex ) / 2 ) + leftIndex
pivotValue := arr[ pivotIndex ]
if layer > 15
Msgbox leftIndex "`n" pivotIndex "`n" rightIndex
Loop {
While( leftIndex < pivotIndex && cmp := compareFn.Call( arr[ leftIndex ], pivotValue ) <= 0 )
leftIndex++
if ( pivotIndex <= leftIndex ) {
pivotIndex := leftIndex
break
}
While( rightIndex > pivotIndex && compareFn.Call( arr[ rightIndex ], pivotValue ) >= 0 )
rightIndex--
if ( pivotIndex >= rightIndex ) {
pivotIndex := rightIndex
break
}
swap( leftIndex, rightIndex )
leftIndex++
rightIndex--
}
if ( leftIndex = pivotIndex ) {
if ( rightIndex > pivotIndex ) {
while ( rightIndex > pivotIndex ) {
if ( compareFn.Call( arr[ rightIndex ], pivotValue ) < 0 ) {
move( rightindex, pivotIndex ), pivotIndex++
} else
rightIndex--
}
}
}
else if ( rightIndex = pivotIndex ) {
while ( leftIndex < pivotIndex ) {
if ( compareFn.Call( arr[ leftIndex ], pivotValue ) > 0 ) {
move( leftIndex, pivotIndex ), pivotIndex--
} else
leftIndex++
}
}
quickSort( firstIndex, pivotIndex - 1 )
quickSort( pivotIndex + 1, lastIndex )
}
insertSort( firstIndex, lastIndex ) {
Loop lastIndex - firstIndex {
currentIndex := firstIndex + A_Index
currentValue := arr[ currentIndex ]
Loop {
currentCompareIndex := currentIndex - A_Index
}Until currentCompareIndex < firstIndex || compareFn.Call( currentValue, arr[currentCompareIndex] ) >= 0
move( currentIndex, currentCompareIndex + 1 )
}
}
standardCompare( compareVal1, compareVal2 ) {
if ( compareVal1 = compareVal2 )
return 0
minStrLen := min( compareLen1 := StrLen( compareVal1 ), StrLen( compareVal2 ) )
Loop minStrLen {
compareChr1 := ord( subStr( compareVal1, A_Index, 1 ) )
compareChr2 := ord( subStr( compareVal2, A_Index, 1 ) )
if ( compareChr1 != compareChr2 )
return compareChr1 - compareChr2
}
return ( ( compareLen1 = minStrLen ) && -1 )
}
swap( index1, index2 ) {
temp := arr[ index1 ]
arr[ index1 ] := arr[ index2 ]
arr[ index2 ] := temp
}
move( srcIndex, targetIndex ) {
if srcIndex != targetIndex
arr.insertAt( targetIndex, arr.RemoveAt( srcIndex ) )
}
}The arguments are the same. The compare function is also optional. The default compare function is standardCompare. Here you can see how a compare function should look like:
It should accept 2 values and return which of the values is larger/smaller. If the first value is smaller return a negative number - if it's the second return a positive number - if they are the same return 0.
The sort function will then sort the array according to the order set by the compare function.
By default the function sorts by how the string of the value looks like.
This is a first draft as to how the syntax should look like - it currently uses a quick sort algorythm which is actually pretty fast.
I hope that this will be a thing in AutoHotkey natively in the future.
Here are some examples:
Code: Select all
#Include sort.ahk
MsgboxDispObj( sort( ["c", "b", "a", "d", "D"] ) ) ;[ "a", "b", "c", "d", "D" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ] ) ) ;[ "1", "11", "2", "3", "4", "5" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ], (a,b) => a-b ) ) ;[ "1", "2", "3", "4", "5", "11" ]
MsgboxDispObj( sort( [3, 5, 1, 4, 2, 11 ], (a,b) => b-a ) ) ;[ "11", "5", "4", "3", "2", "1" ]
MsgboxDispObj( obj ) {
resultStr := "[ "
for each, val in obj
resultStr .= "`"" val "`", "
resultStr := subStr( resultStr, 1, -2 ) . " ]"
msgbox( resultStr )
return resultStr
}Code: Select all
#Include sort.ahk
toSort := []
Loop 100000
toSort.Push( random( -0x80000000, 0x7FFFFFFF ) )
FileDispObj( "sort.log", sort( toSort, (a,b) => a-b ) )
FileDispObj( fileName, obj ) {
resultStr := ""
for each, val in obj
resultStr .= val "`n"
fileOpen( fileName, "w" ).write( resultStr )
return resultStr
}
