[v2 Function]Sort function - replace the built in one with something useable

Post your working scripts, libraries and tools
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

[v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 10:09

Sort()

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 )
The function accepts 2 parameters. First is the array whose data should be sorted. Second is a function that compares 1 of the arrays values to the other and returns that value.
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
}
Recommends AHK Studio
User avatar
kczx3
Posts: 1528
Joined: 06 Oct 2015, 21:39

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:16

Thanks for this. As a JavaScript developer, I certainly prefer using sort as a method on the Array/Object prototype versus just a function.

On a somewhat related note, what does using nested functions gain in this scenario? Or were you just trying to showcase the new stuff in the latest v2 build?
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:44

Well I will add more nested functions as time goes on and I don't want to waste global function name space.
I'm currently trying to implement quickSort.
Recommends AHK Studio
User avatar
kczx3
Posts: 1528
Joined: 06 Oct 2015, 21:39

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 11:57

Ok, that makes sense. Though I suppose you could also create a class instead of using nested functions. Good Work as usual.
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 13:00

I added a quicksort algorythm.
It's now a lot faster - you can check the speed with the second example I added.
Recommends AHK Studio
Helgef
Posts: 4676
Joined: 17 Jul 2016, 01:02
Contact:

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 13:49

Nice, nnnik, thanks for sharing.

There was another quick sort implementation here: Sort dense arrays or matrices. I've used qsort (msdn) for comobjarrays in the past, I made a version for ahk arrays. To note, it copies the array, but it is a very simple implementation.

Code: Select all

; qsort
qsort(arr, cmpfn){
	static VT_UI4 := 0x13
	static sizeofInt := 4
	local r := [] ; return array
	local l := arr.length()
	if !l
		return r
	r.setcapacity(l)
	; Create index array
	local da := comobjarray(VT_UI4, l) ; array of l uints
	loop l
		da[a_index-1] := a_index
	; Get pointer to the index array
	local SAFEARRAY := ComObjValue(da)
	local pvData := NumGet(SAFEARRAY, 12+(A_PtrSize=4?0:4), "Ptr")
	; dllcall qsort
	local pcmp := callbackcreate("cmp", "cdecl f", 2)
	DllCall("MSVCRT.dll\qsort", "Ptr", pvData, "Ptr", l, "Ptr", sizeofInt, "Ptr", pcmp, "cdecl")
	callbackfree(pcmp)
	; assemble result
	local k
	for k in da
		r[a_index] := arr[k]
	return r
	cmp(a,b){	; go between function
		return cmpfn.call(arr[ numget(a, "uint") ], arr[ numget(b, "uint") ])
	}
}
; test
stringcasesense c:=["on", "off", "locale"][random(1,3)]
for k, v in qsort(["x", "a", "B", "Ö", "o", "ö"], (a, b) => a < b ? -1 : a > b ? 1 : 0)
	str .= v "`n" 
msgbox str "`n`n`ncase:`t" c 
Cheers
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 14:02

Well yeah I can't use a version thats dedicated for matrices. Also my version would be best with C++ arrays rather than AHK objects.
But yeah using MSDNs quicksort might be faster at a specific stage.

I also plan to further enhacne it's speed but I don't want to do more today.
A little bit of reading:
http://algo2.iti.kit.edu/sanders/papers/KalSan06.pdf
Recommends AHK Studio
User avatar
BGM
Posts: 507
Joined: 20 Nov 2013, 20:56
GitHub: bgmCoder
Contact:

Re: [v2 Function]Sort function - replace the built in one with something useable

28 Mar 2018, 14:12

Here are my three favourites that I use - I learned them from a language called BCX and now I recreate them in any language in which I write any code.

LEFT and RIGHT with a little twist I call "shift"

Code: Select all

;returns the rightmost number of characters
;if shift is true, then return the string with the number of characters removed
;example := right(123abc, 2, true)
;result:  bc
;example := right(123abc, 2, false)
;result: 123a
right(whattext, numchars=1, shift=false){
	StringLen, thislen, whattext
	numchars := abs(numchars) ;remove the negativity!
	if(shift){
		thisstring := substr(whattext, 1, thislen - numchars)
	}else{
		thisstring := substr(whattext, thislen - numchars +1, thislen)
	}
	return thisstring
}

Code: Select all

;returns the leftmost number of characters
;if shift is true, then return the string with the number of characters removed - that is, shift = trim
left(whattext, numchars=1, shift=false){
	StringLen, thislen, whattext
	numchars := abs(numchars) ;remove the negativity!
	if(shift){
		thisstring := substr(whattext, numchars+1, thislen)
	}else{
		thisstring := substr(whattext, 1, numchars)
	}
	return thisstring
}
And for this one, well, no, nobody really needs a wrapper for msgboxes. But after I got used to javascript, I wanted to use alertfor everything. So I sort of customized msgbox to do my typical routines.
alert("bob was here")

Code: Select all

/*!
	Function: alert(whatmessage, whaticon="", whattitle="", whattimeout="")
		A Wrapper for messagebox with intuitive parameters
	Parameters:
		whatmessage - What you want to say
		whaticon - The icon you like.  Leave blank for no icon.  
			You can specify: "asterisk", "exclamation", "warning", "hand", "stop", "error", "question", "help", "okay" or blank.
		whattitle - Your custom title for the messagebox window
		whattimeout - When you want the messagebox to disappear on it own; leave blank to have it not disappear.
	Returns: none
	Notes: If the original window is topmost, this messagebox will also be topmost
*/
alert(whatmessage, whaticon="", whattitle="", whattimeout=""){
	if(!whattitle){	;use the apptitle variable if it is defined
		wingettitle, whattitle, A
	}
	if(whaticon = "asterisk")
		theseoptions := 64
	else if(whaticon = "exclamation" || whaticon = "warning")
		theseoptions := 48
	else if(whaticon = "hand" || whaticon = "stop" || whaticon = "error")
		theseoptions := 16
	else if(whaticon = "help" || whaticon = "question")
		theseoptions := 32
	else if(whaticon = "okay")
		theseoptions := 0
	else
		theseoptions := 0
		
	;if the original window is topmost, make this here msgbox topmost, too, so it doesn't disappear behind the window
	WinGet, ExStyle, ExStyle, a
	if (ExStyle & 0x8){  ; 0x8 is WS_EX_TOPMOST.
		theseoptions := theseoptions + 4096
	}	
	
	;the "options" number must be a forced expression
	msgbox, % theseoptions, %whattitle%, %whatmessage%, %whattimeout%			;%
}
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

29 Mar 2018, 09:43

Hm yeah looks good.
I think I'm going to add another one:

Code: Select all

Select( arr, selectionFn ) {
	local
	toRemove := []
	for key, element in arr
		if !selectionFn.call( element )
			toRemove.insertAt( 1, key )
	for each, key in toRemove
		arr.removeAt( key )
	return arr
}
Example:

Code: Select all

#Include Select.ahk
MsgboxDispObj( Select( [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], (nr)=>!mod(nr, 3) ) ) ;[ "3", "6", "9", "0" ]

MsgboxDispObj( obj ) {
	resultStr := "[ "
	for each, val in obj
		resultStr .= "`"" val "`", " 
	resultStr := subStr( resultStr, 1, -2 ) . " ]"
	msgbox( resultStr )
	return resultStr
}
Recommends AHK Studio
User avatar
nnnik
Posts: 4497
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: [v2 Function]Sort function - replace the built in one with something useable

29 Mar 2018, 10:54

Yeah. Select comes from SQL though
Recommends AHK Studio
freespacing
Posts: 148
Joined: 28 Sep 2016, 11:14
Contact:

Re: [v2 Function]Sort function - replace the built in one with something useable

08 Feb 2021, 09:38

Helgef wrote:
28 Mar 2018, 13:49
I made a version for ahk arrays. To note, it copies the array, but it is a very simple implementation.
@Helgef Your code is way over my head, but I'm extremely interested in it because my own QuickSort recurses and fails for large lists.

Would you be willing to share a version compatible wity Autonotkey v.1?
The one you posted gives me this error message:
Line Text: cmp(a,b)
Error: Functions cannot contain functions.

The program will exit.
Thank you for sharing your very fancy code, have a great week.
braunbaer
Posts: 473
Joined: 22 Feb 2016, 10:49

[V1.1 Function]Sort function - replace the built in one with something useable

28 Mar 2021, 21:53

Hi!
I have adapted the sort function to run on AHK Version 1.1, because I have not yet switched to AHK V2 and needed an array sort for one of my projects. Also made some minor changes.
Big thanks to nnnik for this great routine

It now makes an inplace sort, to avoid the need for copying big arrays. The array is passed byref. If you want to keep the original array, you have to copy it before calling sort.
The compare callback function now also uses ByRef parameters, which should increase speed if the size of the array elements is big.
Removed insertsort, all arrays are quicksorted, even smaller ones.

Code: Select all

/* written by nnnik, adapted for AHK V1.1 by braunbaer
	https://autohotkey.com/boards/viewtopic.php?f=6&t=46260
	v1.1.0 
	Changelog:
	v0.1.0 Implemented an example using insertion sort
	v1.0.0 It now uses quick sort
	v1.1.0 Adapted for V1.1, make inplace sort
*/
sort( byref arr, compareFn := "" ) {
    if !compareFn
        compareFn := func( "standardCompare" )
    quickSort( Arr, Arr.MinIndex(), Arr.MaxIndex(), compareFn )
    }

quickSort( byref arr, firstIndex, lastIndex, compareFn ) {
    if (LastIndex-Firstindex<2){
        if (LastIndex<=firstIndex)
            return
        if compareFn.Call( arr[ FirstIndex ], arr[ lastIndex ] ) > 0
            sortswap(Arr, FirstIndex, LastIndex)
        return
        }

    leftIndex  := firstIndex
    rightIndex := lastIndex
    pivotIndex := ( rightIndex - leftIndex ) // 2  + leftIndex
    pivotValue := arr[ pivotIndex ]

    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
            }
        sortswap( arr, leftIndex, rightIndex )
        leftIndex++
        rightIndex--
        }

    if ( leftIndex = pivotIndex ) {
        if ( rightIndex > pivotIndex ) {
            while ( rightIndex > pivotIndex ) {
                if ( compareFn.Call( arr[ rightIndex ], pivotValue ) < 0 ) {
                    sortmove( arr, rightindex, pivotIndex ), pivotIndex++
                    } else
                    rightIndex--
                }
            }
        }
    else if ( rightIndex = pivotIndex ) {
        while ( leftIndex < pivotIndex ) {
            if ( compareFn.Call( arr[ leftIndex ], pivotValue ) > 0 ) {
                sortmove( arr, leftIndex, pivotIndex ), pivotIndex--
                } else
                leftIndex++
            }
        }
    quickSort( Arr, firstIndex, pivotIndex - 1, compareFn )
    quickSort( arr, pivotIndex + 1, lastIndex, compareFn )
    }

standardCompare(Byref compareVal1, ByRef compareVal2) {
    if ( compareVal1 = compareVal2 )
         return 0
    if ( compareVal1 > compareVal2 )
         return 1
    return -1
    }

sortswap( byref arr, index1, index2 ) {
    temp := arr[ index1 ], arr[ index1 ] := arr[ index2 ], arr[ index2 ] := temp
    }

sortmove( byref arr, srcIndex, targetIndex ) {
    if srcIndex != targetIndex
        arr.insertAt( targetIndex, arr.RemoveAt( srcIndex ) )
    }
User avatar
rommmcek
Posts: 1416
Joined: 15 Aug 2014, 15:18

Re: [v2 Function]Sort function - replace the built in one with something useable

29 Mar 2021, 15:33

Thanks for v1.1 version, works fine.
Here is more condensed (and quicker) approach (didn't check if results are always 100% the same, but generally does the job):

Code: Select all

a := ["carrots", "ban01anas", 204, "ban4anas", "ban1anas", 24, "apples",5,25,54,4,1,52,24]

; ====== actual soring starts ================
b:= Srt(a)

Srt(a) {
    for i, j in (a, b:= [])
        b[j]? "": b[j]:= [], b[j].Push(j)
    Return b
}
; ====== actual soring ends ================

; ====== auxiliary functions & coding ===========
; dissolve the result
for i, j in (b, ca:= [])
    for k, v in j
        c.= v "`n", ca.Push(v) ; optionally convert to one dimensional array

pa(b), pa(c), pa(ca)
Return

txtArr(r, i:="  ", d:=0, b:="") {
	For k, v in (r, IsObject(r)? "": e:= 1)
		c.= IsObject(v)? b k ":`n" txtArr(v, i, d+1, b i): b k ": " v "`n", d>0? "": t:=c
    Return e? r: d>0? c: t
}
pa(in) {
    MsgBox % txtArr(in)
}
P.s.: For large arrays it would make sens to replace for i, j in (a, b:= []) with for i, j in (a, b:= [], b.SetCapacity(a.MaxIndex()))

Return to “Scripts and Functions”

Who is online

Users browsing this forum: KruschenZ, Nextron and 31 guests