it's been a while since i posted but here goes...
I've been experimenting with recursive programming and I came across a sorting method called "Quick Sort". It sorts lists with an n Log(n) complexity.
Code:
#NoEnv ; Recommended for performance and compatibility with future AutoHotkey releases.
SendMode Input ; Recommended for new scripts due to its superior speed and reliability.
SetWorkingDir %A_ScriptDir% ; Ensures a consistent starting directory.
;Written By SpiderGames
;test := [46,23,99,55,1,2,3,4,5,6,55]
;sortedTest := QSort(test,1)
;msgbox % sortedTest.MaxIndex()
;Loop % sortedTest.MaxIndex()
; MsgBox % sortedTest[A_Index]
QSort(toSort,Direction = 1)
{
if (Direction != 1)
Direction = -1
if (toSort.MaxIndex() < 2)
return % toSort
leftSide := Object()
rightSide := Object()
pivotPoint := toSort.Remove(1)
loop % toSort.MaxIndex()
{
if(toSort[A_Index]**Direction > pivotPoint**Direction)
leftSide.Insert(toSort[A_Index])
else
rightSide.Insert(toSort[A_Index])
}
leftSide := QSort(leftSide,Direction)
rightSide := QSort(rightSide,Direction)
leftSide.Insert(pivotPoint)
Loop % rightSide.MaxIndex()
leftSide.Insert(rightSide[A_Index])
return % leftSide
}
However when i ran a test sample of 5000 randomly generated numbers the AHK build in function sort sorted it in 37ms while my QSort took 350ms at least i beat bubble sort :3 which had a time of 5200ms
My question is what is the complexity of "Sort".
also i believe the following block is slowing down my algorithm any suggestions on how to improve it?
Code:
leftSide := QSort(leftSide,Direction)
rightSide := QSort(rightSide,Direction)
leftSide.Insert(pivotPoint)
Loop % rightSide.MaxIndex()
leftSide.Insert(rightSide[A_Index])
return % leftSide
_________________
I know i have 6 legs. It's cuz I'm special.
Login
Register
FAQ
Search
