Recursionless Quicksort

[ezzetabi]

Need to sort?

Yet an other way to do it...

Testing code

opt ('MustDeclareVars', 1)
Local $c, $a[1000], $msg = ''

For $c = 0 To UBound($a) - 1
   $a[$c] = Random(0, 10000, 1)
Next

MsgBox(0, 'Start.', 'Press OK to start')
_Quicksort($a, 0, UBound($a) - 1)
MsgBox(0, 'Done.', 'Done')

For $c = 0 To UBound($a) - 1
   $msg = $msg & $a[$c] & ' '
Next

MsgBox(0, 'Results:', $msg)

Exit

Functions theirselves...

expandcollapse popup

Func _Quicksort(ByRef $a, $p, $r)
   Local $j, $q
   $j = int(log($r - $p) / log(2)) * 2 + 2
   Local $stk[$j], $ls = 0
   
   While 1
      While $p < $r
        ;__qs_swap($a[Random($p, $r, 1) ], $a[$r]);<- Uncomment this if your array is already almost sorted
         $q = $p - 1
         For $j = $p To $r - 1
            If $a[$j] <= $a[$r] Then;<-------------- Edit here if you want change sorting condition
               $q = $q + 1
               __qs_swap($a[$q], $a[$j])
            EndIf
         Next
         $q = $q + 1
         __qs_swap($a[$q], $a[$r])
         
         If $r - $q > $q - $p Then
            __qs_stk_push($q + 1, $stk, $ls)
            __qs_stk_push($r, $stk, $ls)
            $r = $q - 1
         Else
            __qs_stk_push($p, $stk, $ls)
            __qs_stk_push($q - 1, $stk, $ls)
            $p = $q + 1
         EndIf
      WEnd
      
      $r = __qs_stk_pop($stk, $ls)
      If @error Then ExitLoop
      $p = __qs_stk_pop($stk, $ls)
   WEnd
EndFunc  ;==>_Quicksort

Func __qs_swap(ByRef $st, ByRef $nd)
   Local $t = $nd
   $nd = $st
   $st = $t
EndFunc  ;==>__qs_swap

Func __qs_stk_pop(ByRef $stk, ByRef $ls)
   If $ls = 0 Then
      SetError(1)
      Return 0
   EndIf
   $ls = $ls - 1
   Return $stk[$ls]
EndFunc  ;==>__qs_stk_pop

Func __qs_stk_push($value, ByRef $stk, ByRef $ls)
   $stk[$ls] = $value
   $ls = $ls + 1
EndFunc  ;==>__qs_stk_push

Edit: A little improvement

Edit2: Should be faster now. The __qs_swap($a[Random($p, $r, 1) ], $a[$r]) line is commented since it is often only a loss of speed. But... If you array is already almost sorted (or reversely sorted) it will speed up a lot.

Try this code with the line commented and uncommend:

opt ('MustDeclareVars', 1)
Local $c, $a[1000], $msg = ''

For $c = 0 To UBound($a) - 1
   $a[$c] = $c
Next

MsgBox(0, 'Start.', 'Press OK to start')
_Quicksort($a, 0, UBound($a) - 1)
MsgBox(0, 'Done.', 'Done')

For $c = 0 To UBound($a) - 1
   $msg = $msg & $a[$c] & ' '
Next

MsgBox(0, 'Results:', $msg)
Exit

Edited May 16, 2005 by ezzetabi

[steveR]

Nice ezzetabi, thanks.

[bluebearr]

Wow, I did some comparison with _ArraySort. _Quicksort returned results in about 1.8 secs, whereas _ArraySort consistently took 16-18 seconds.

Faster = better

BlueBearr

[ezzetabi]

About pure speed probably the fastest way is using the recursion removal tecnique on only one of the two _quicksort recursions calls...

If you want to test:

Quicksort with only a recursion call removed:

Func _Quicksort(ByRef $a, $p, $r)
   Local $j, $q
   
   While $p < $r
     ;__qs_swap($a[Random($p, $r, 1) ], $a[$r]);<- Uncomment this if your array is already almost sorted
      $q = $p - 1
      For $j = $p To $r - 1
         If $a[$j] <= $a[$r] Then;<-------------- Edit here if you want change sorting condition
            $q = $q + 1
            __qs_swap($a[$q], $a[$j])
         EndIf
      Next
      $q = $q + 1
      __qs_swap($a[$q], $a[$r])
      
      _Quicksort($a, $q + 1, $r)
      $r = $q - 1
   WEnd
EndFunc  ;==>_Quicksort

Func __qs_swap(ByRef $st, ByRef $nd)
   Local $t = $nd
   $nd = $st
   $st = $t
EndFunc  ;==>__qs_swap

[ezzetabi]

...and the classical _quicksort:

Func _Quicksort(ByRef $a, $p, $r)
   If $p < $r Then
      Local $j, $q
    ;__qs_swap($a[Random($p, $r, 1) ], $a[$r]);<- Uncomment this if your array is already almost sorted
      $q = $p - 1
      For $j = $p To $r - 1
         If $a[$j] <= $a[$r] Then;<-------------- Edit here if you want change sorting condition
            $q = $q + 1
            __qs_swap($a[$q], $a[$j])
         EndIf
      Next
      $q = $q + 1
      __qs_swap($a[$q], $a[$r])
      
      _Quicksort($a, $q + 1, $r)
      _Quicksort($a, $p, $q - 1)
   EndIf
EndFunc  ;==>_Quicksort

Func __qs_swap(ByRef $st, ByRef $nd)
   Local $t = $nd
   $nd = $st
   $st = $t
EndFunc  ;==>__qs_swap

Edited May 16, 2005 by ezzetabi

[buzz44]

Can you please tell me what advantages/disadvantages this has over _ArraySort(). Speed never used to be an important factor for me in scripting but on my current project I need to sort a list view containing hundereds of items. And the funciton I use to sort must be able to sort and reverse it if told to. Thanks ezzetabi. Also what does $a, $p, $r mean. $a Is the array you want to sort. $p is ? and $r is the number of elements?

[ezzetabi]

I never said it has advantages. It is just sintax sugar.

$a is the array you want to sort

$p is where begin the peice of array to sort (usually 0 or 1)

$r is where finish the peice of array to sort (usually Ubound($a)-1 or $a[0])

$p and $r are important since often autoit scripts leave the position 0 for special purpuses and of course it should not be sorted.

About reverse I wrote a big comment like "Edit here if you want change sorting condition", just change <= to >=

Edited May 17, 2005 by ezzetabi

[buzz44]

I should have refraised it differently. What are the differences between this and _ArraySort() besides the speed? Does it use the Shell Sort algorithm like _ArraySort() or a different method? Please excuse me if I'm being interrorgating but I would jsut like to know these answers.

What I really need to know is if it will sort data like, 'Something here|AAA|BBB|CC|DDD' and return the same result as _ArraySort() does, Thanks.

Edited May 18, 2005 by Burrup

[ezzetabi]

I never used _Arraysort. But I see no reason why the order should be different if a<b in Arraysort is also a<b in Quicksort.

My question is, why you do not try?!?

Order is based over the operator you set in the famous line "Edit here... bla bla", Arraysort probably have something similar.

About the algorithm... It is almost banal saying that _Quicksort use... QUICKSORT ALGORITHM! Quicksort is often (average case) the fastest algorithm avaiable. In the worst case (array already sorted or reversed) there is a variant: the randomized quicksort that obtains excellent speeds anyway, in my script it is obtained uncommenting the line marked as "Uncomment here...".

I do not want to be hateful... but TRY to read the code before making stupid questions, I would calling the func ShellSort if it used the shell sort, don't you think?

Edited May 18, 2005 by ezzetabi

[buzz44]

I merely thought that you usually give a function its name by what it does... in this case it sorts... quickly and was unaware that there as infact a quicksort algorithm. Why dont they call _ArraySort() ShellSort then??? Don't you think.

Edit: I have tested. _ArraySort() is about 40-60 ms, where your 'quicksort' can range from 500-800ms.

Edited May 18, 2005 by Burrup

[ezzetabi]

I did not give the name to _ArraySort function. Do not blame me.

About your tests... It is a pity you did not posted testing conditions.

Try this:

expandcollapse popup

opt ('MustDeclareVars', 1)
Local $size = 1000
Local $numberoftests = 5


Local $as[$size], $qs
Local $dt, $msg = '', $t
Local $c, $c2

For $c2 = 1 To $numberoftests
   For $c = 1 To $size - 1;<-- Fill the array with random numbers
      $as[$c] = Random(0, 30000, 1)
   Next
   $qs = $as;<- The starting arrays are set as the same
   
   $t = TimerInit();<- Testing quicksort
   _Quicksort($qs, 0, $size - 1)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- Quicksort ' & @LF
   ToolTip(StringTrimRight($msg,1))
   
   $t = TimerInit();<- Testing ArraySort
   _ArraySort($as)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- ArraySort ' & @LF
   ToolTip(StringTrimRight($msg,1))
Next
Sleep( 10000 )

Func _Quicksort(ByRef $a, $p, $r)
   Local $j, $q
   $j = int(log($r - $p) / log(2)) * 2 + 2
   Local $stk[$j], $ls = 0
   
   While 1
      While $p < $r
        ;__qs_swap($a[Random($p, $r, 1) ], $a[$r]);<- Uncomment this if your array is already almost sorted
         $q = $p - 1
         For $j = $p To $r - 1
            If $a[$j] <= $a[$r] Then;<-------------- Edit here if you want change sorting condition
               $q = $q + 1
               __qs_swap($a[$q], $a[$j])
            EndIf
         Next
         $q = $q + 1
         __qs_swap($a[$q], $a[$r])
         
         If $r - $q > $q - $p Then
            __qs_stk_push($q + 1, $stk, $ls)
            __qs_stk_push($r, $stk, $ls)
            $r = $q - 1
         Else
            __qs_stk_push($p, $stk, $ls)
            __qs_stk_push($q - 1, $stk, $ls)
            $p = $q + 1
         EndIf
      WEnd
      
      $r = __qs_stk_pop($stk, $ls)
      If @error Then ExitLoop
      $p = __qs_stk_pop($stk, $ls)
   WEnd
EndFunc;==>_Quicksort

Func __qs_swap(ByRef $st, ByRef $nd)
   Local $t = $nd
   $nd = $st
   $st = $t
EndFunc;==>__qs_swap

Func __qs_stk_pop(ByRef $stk, ByRef $ls)
   If $ls = 0 Then
      SetError(1)
      Return 0
   EndIf
   $ls = $ls - 1
   Return $stk[$ls]
EndFunc;==>__qs_stk_pop

Func __qs_stk_push($value, ByRef $stk, ByRef $ls)
   $stk[$ls] = $value
   $ls = $ls + 1
EndFunc;==>__qs_stk_push

Func _ArraySort(ByRef $a_Array, $i_Decending = 0, $i_Base = 0, $i_UBound = 0, $i_Dim = 1, $i_SortIndex = 0)
   Local $A_Size, $Gap, $Count, $Temp, $C_Dim
   Local $b_ExchangeValues = 0
   Local $IsChanged = 0
   
  ; Set to ubound when not specified
   If $i_UBound < 1 Then $i_UBound = UBound($a_Array) - 1
   
   If UBound($a_Array) <= $i_UBound Or Not IsNumber($i_UBound) Then
      SetError(1)
      Return 0
   EndIf
  ; Shell sort array
   $A_Size = $i_UBound
   $Gap = Int($A_Size / 2)
   $b_ExchangeValues = 0
   $IsChanged = 0
  ;
   While $Gap <> 0
      $IsChanged = 0
      For $Count = $i_Base To ($A_Size - $Gap)
         $b_ExchangeValues = 0
         If $i_Dim = 1 Then
            If $i_Decending <> 1 Then; sort array Ascending
               If $a_Array[$Count] > $a_Array[$Count + $Gap] Then
                  $b_ExchangeValues = 1
               EndIf
            Else; sort array Descending
               If $a_Array[$Count] < $a_Array[$Count + $Gap] Then
                  $b_ExchangeValues = 1
               EndIf
            EndIf
            If ($b_ExchangeValues) Then
               $Temp = $a_Array[$Count]
               $a_Array[$Count] = $a_Array[$Count + $Gap]
               $a_Array[$Count + $Gap] = $Temp
               $IsChanged = 1
            EndIf
         Else
            If $i_Decending <> 1 Then; sort array Ascending
               If $a_Array[$Count][$i_SortIndex] > $a_Array[$Count + $Gap][$i_SortIndex] Then
                  $b_ExchangeValues = 1
               EndIf
            Else; sort array Descending
               If $a_Array[$Count][$i_SortIndex] < $a_Array[$Count + $Gap][$i_SortIndex] Then
                  $b_ExchangeValues = 1
               EndIf
            EndIf
            If ($b_ExchangeValues) Then
               For $C_Dim = 0 To $i_Dim - 1
                  $Temp = $a_Array[$Count][$C_Dim]
                  $a_Array[$Count][$C_Dim] = $a_Array[$Count + $Gap][$C_Dim]
                  $a_Array[$Count + $Gap][$C_Dim] = $Temp
                  $IsChanged = 1
               Next
            EndIf
         EndIf
      Next
    ; If no changes were made to array, decrease $gap size
      If $IsChanged = 0 Then
         $Gap = Int($Gap / 2)
      EndIf
   WEnd
   Return 1
EndFunc  ;==>_ArraySort

Most probably you tested quicksort in array already sorted where quicksort is very slow, but it is expected (did you really read my last message?)

opt ('MustDeclareVars', 1)
Local $size = 1000
Local $numberoftests = 5


Local $as[$size], $qs
Local $dt, $msg = '', $t
Local $c, $c2

For $c2 = 1 To $numberoftests
   For $c = 1 To $size - 1;<-- Makes an already sorted array
      $as[$c] = $c
   Next
   $qs = $as;<- The starting arrays are set as the same
   
   $t = TimerInit();<- Testing quicksort
   _Quicksort($qs, 0, $size - 1)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- Quicksort ' & @LF
   ToolTip(StringTrimRight($msg,1))
   
   $t = TimerInit();<- Testing ArraySort
   _ArraySort($as)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- ArraySort ' & @LF
   ToolTip(StringTrimRight($msg,1))
Next
Sleep( 10000 )

;Function removed for brevity

In those cases, it is a good idea using the randomized variation:

Where, by the way, quicksort is still faster.

expandcollapse popup

opt ('MustDeclareVars', 1)
Local $size = 1000
Local $numberoftests = 5


Local $as[$size], $qs
Local $dt, $msg = '', $t
Local $c, $c2

For $c2 = 1 To $numberoftests
   For $c = 1 To $size - 1;<-- Makes an already sorted array
      $as[$c] = $c
   Next
   $qs = $as;<- The starting arrays are set as the same
   
   $t = TimerInit();<- Testing quicksort
   _Quicksort($qs, 0, $size - 1)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- Quicksort ' & @LF
   ToolTip(StringTrimRight($msg,1))
   
   $t = TimerInit();<- Testing ArraySort
   _ArraySort($as)
   $dt = Round(TimerDiff($t), 2)
   $msg = $msg & $dt & ' <- ArraySort ' & @LF
   ToolTip(StringTrimRight($msg,1))
Next
Sleep( 10000 )

Func _Quicksort(ByRef $a, $p, $r)
   Local $j, $q
   $j = int(log($r - $p) / log(2)) * 2 + 2
   Local $stk[$j], $ls = 0
   
   While 1
      While $p < $r
         __qs_swap($a[Random($p, $r, 1) ], $a[$r])
         $q = $p - 1
         For $j = $p To $r - 1
            If $a[$j] <= $a[$r] Then;<-------------- Edit here if you want change sorting condition
               $q = $q + 1
               __qs_swap($a[$q], $a[$j])
            EndIf
         Next
         $q = $q + 1
         __qs_swap($a[$q], $a[$r])
         
         If $r - $q > $q - $p Then
            __qs_stk_push($q + 1, $stk, $ls)
            __qs_stk_push($r, $stk, $ls)
            $r = $q - 1
         Else
            __qs_stk_push($p, $stk, $ls)
            __qs_stk_push($q - 1, $stk, $ls)
            $p = $q + 1
         EndIf
      WEnd
      
      $r = __qs_stk_pop($stk, $ls)
      If @error Then ExitLoop
      $p = __qs_stk_pop($stk, $ls)
   WEnd
EndFunc;==>_Quicksort
;Other functions the same

You can't win against math.

Edited May 18, 2005 by ezzetabi

[mrider]

ezzetabi:

Going back to your O.P. I'm putting the finishing touches on a hash* include file. I used the traditional QuickSort algorithm for sorting, pretty much straight down the line - including scrambling the input, using recursion, blah, blah, blah.

Have you found an advantage to the non-recursion algorithm in your testing? I like your code - and will shamelessly duplicate it if it works better.

* Aka "associative array", "map", "key->value pairing",...

EDIT: Oh, and BTW, you can always do a single pass through the array looking for an item out of order - jumping out of the loop if such an item is found. This pretty much negates any speed advantage of the other sort types for cases when the array is often 100% sorted.

Edited May 18, 2005 by mrider

[ezzetabi]

Autoit's stack can't overtook 384 calls, in big arrays classical quicksort may give stack overflow error.

Recursionless version of course won't. Moreover selecting what putting in the 'homemade' stack, it should never contain more than twice the logarithm (base 2) of the number of elements.

So even in large arrays it won't use much memory.

(if the number of elements become the square, the stack is only twice as big)

What does OP mean?

An hash table is a good idea! Thanks to you.

[mrider]

Man you're quick. You posted while I was editing

O.P. means Original Post or Original Poster (person) depending on how it's used.

Autoit's stack can't overtook 384 calls

Didn't know that. I tested the reference algorithm that I wrote in Java with 1,000,000 items. So far I've only tested my hash with around 1000 items.

Looks like I'll be going back to the code...

[buzz44]

I did not give the name to _ArraySort function. Do not blame me.

I did not blame you so please don't insist. If you bothered to read my previous post you would realise that I was not referring to you when I said 'they' and was referring to the devs.

_ArraySort() is still returning faster. I'm afraid I cant use your function as there are to many 'factors' that effect its speed. I'm using this to sort a list view by header. So as you click each different header it will sort it, if clicked again it will reverse. This means there is a pretty random chance of the array being sorted/nearly sorted/ or all you have to do is reverse it, which all depends on which column heads you press etc.

[ezzetabi]

can you PLEASE tell your testing condition?

Post CODE not empty words.

[buzz44]

Well seing as its a work in progress and I don't want to release an source yet, no. But what I'm sorting looks like

"AAA|BBB|CCC|DDD|EEE|FFF|GGG|HHH"

Where AAA/BBB..HHH etc will be a number or a letter. It contains spaces in them like, "AA A A" and theres about 95 of them in a random order in the array. I made a copy of the original array. I timed the original using _ArraySort() and then I timed it again, this time using _QuickSort() and the copied array.

Edited May 19, 2005 by Burrup

[ezzetabi]

Other test:

expandcollapse popup

opt ('MustDeclareVars', 1)
Local $iNumberofTests = 5
Local $iLenghtofStrings = 100
Local $iNumberofStrings = 1000

Local $as, $qs
Local $msg = '', $c
Local $t, $dtq, $dta

#cs
  ;Uncomment if you want seeing the random strings.
   For $c= 0 to UBound($qs) - 1
   $msg = $msg & $qs[$c] & @LF
   Next
   MsgBox(0,'',$msg)
#ce

For $c = 1 To $iNumberofTests
   $qs = _RandomText($iLenghtofStrings, $iNumberofStrings)
   $as = $qs
   
   $t = TimerInit()
   _Quicksort($qs, 0, UBound($qs) - 1)
   $dtq = TimerDiff($t)
   $msg = $msg & @LF & $dtq & ' <--- _QuickSort  '
   ToolTip(StringTrimLeft($msg, 1))
   
   $t = TimerInit()
   _ArraySort($as)
   $dta = TimerDiff($t)
   $msg = $msg & Round($dtq / $dta, 2) & @LF & $dta & ' <--- _Arraysort  ' & Round($dta / $dtq, 2) & @LF
   ToolTip(StringTrimLeft($msg, 1))
Next
Sleep(10000)

Func _RandomText($iLenght, $iNumber)
   Local $aText[$iNumber], $c, $c2
   
   For $c = 0 To $iNumber - 1
      $aText[$c] = ''
      For $c2 = 1 To $iLenght
         $aText[$c] = $aText[$c] & Chr(Random(32, 255, 1))
      Next
   Next
   Return $aText
EndFunc  ;==>_RandomText

;Copy here _Quicksort and _Arraysort code

Usual result, _Quicksort is 10 times faster.

But since you can't use it correcly... Don't use it.

As I said in the beggining (I was already fearing such posts) it is only sintax sugar. It have no advantages for who can't see them.

[mrider]

Burrup:

Generally speaking, the Quick Sort algorithm is considered the fastest of sorting algorithms. However, depending on the nature of your data, it's entirely possible that another algorithm could be quicker. For example, suppose you have only two items transposed in a large array - in that situation, a Bubble Sort would be fastest since it can straighten out the array in one pass, and would detect that it's sorted in the second pass.

Normally one selects the Quick Sort algorithm when (( A: The data is highly random ) AND ( B: The data set is small enough such that one won't crash the stack)) OR ( C: The layout of the data is unknown)

You, and only you, can determine if your data layout is such that a different sort will work better. It's certainly possible - but it's highly atypical.

ezzetabi:

You'll squeak a teensy bit more speed out of your sort if you add a condition to the swap to return immediately if the left and right elements are equal. Ex:

Func __qs_swap(ByRef $st, ByRef $nd)
   If $st == $nd Then Return; <-- This may help a tiny bit...
   Local $t = $nd
   $nd = $st
   $st = $t
EndFunc;==>__qs_swap

[EDIT] Oh - and P.S. Thanks for the code!

Edited May 19, 2005 by mrider

[ezzetabi]

Thanks for speaking to Burrup, I hope he (she?) understands.

About the swapping idea:

It needs testing, compilers often are already highly optimized for swapping so the cost of the if statement may be greater than the advantage.

Yet... Nice idea, thanks.

Edited May 19, 2005 by ezzetabi