#70350 - 2002-09-27 05:58 PM
Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
This is faster than combsort on my system..
I'm using a quicksort algorithm iteratively with 2 stacks set up to hold pointers to the lower and upper level of each segment being sorted. The size of the stacks could be increased if you were sorting millions of items... but it probably isn't necessary.
What do you guys think? Should I add features/get rid of bad programming pieces?
code:
function qs($a)
DIM $ls[32],$us[32],$sp,$L,$U,$m,$p,$i,$j,$t
$ls[0]=0
$us[0]=UBOUND($a)
$sp=0
While $sp >=0
$l=$ls[$sp]
$u=$us[$sp]
While $L < $U
$p=$L+($U-$L)/2
$t=$a[$L]
$A[$L]=$A[$P]
$A[$P]=$t
$i=$L+1
$j=$U
:L1
While ($i<$j) AND $A[$L] > $A[$i]
$i=$i+1
Loop
While ($j>=$i) AND $A[$j] > $A[$L]
$j=$j-1
Loop
IF $i >= $j goto L2 ENDIF
$t=$A[$i]
$A[$i]=$A[$j]
$A[$j]=$t
$j=$j-1
$i=$i+1
Goto L1
:L2
$t=$a[$l]
$a[$l]=$a[$j]
$a[$j]=$t
$m=$j
If $m-$l <= $u - $m
If $m+1 < $u
$ls[$sp]=$m+1
$us[$sp]=$u
$sp=$sp+1
Endif
$u=$m-1
Else
If $m-1 > $l
$ls[$sp]=$l
$us[$sp]=$m-1
$sp=$sp+1
Endif
$l=$m+1
Endif
Loop
$sp=$sp-1
Loop
$qs=$a
Endfunction
On my system:
at 10,000 random elements:
combsort takes 90% longer
at 1,000 random elements:
combsort takes 50% longer
at 100 random elements:
combsort takes 33% longer
.....
When the number of elements is < 12, quicksort takes longer on average, but still under 20 ticks on a PIII-400/Win95 system.
Brian
P.S. .. anyone want to try to add multi-dimensional array capabilities?
|
|
Top
|
|
|
|
|
#70351 - 2002-09-27 07:02 PM
Re: Super-quick iterative quicksort!!!
|
Shawn
Administrator
Registered: 1999-08-13
Posts: 8611
|
VERY NICE ... findings confirmed on my system ... well done ... put this into the UDF forum for sure ... question: is this "a" quick sort method or "the" quicksort method ? Is there more than one quicksort method ? Wow ... now your talking ... should see if you (we) can improve this algorithm even more ... or is it already optimized. Would take me a week just to understand this puppy ![[Wink]](images/icons/wink.gif)
|
|
Top
|
|
|
|
|
#70352 - 2002-09-27 07:08 PM
Re: Super-quick iterative quicksort!!!
|
Shawn
Administrator
Registered: 1999-08-13
Posts: 8611
|
Could you post a little bit of a $variable "legend" in a seperate post (I know you kept your $variable names short cause it speeds things up) !!! Kinda like :
code:
$a = array
$ls = lower "whatever"
$us = upper "whatever"
[ 27. September 2002, 19:09: Message edited by: Shawn ]
|
|
Top
|
|
|
|
|
#70353 - 2002-09-27 07:51 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
Hmm. I would say this is "the" quicksort method (well, I don't really know, but I'm guessing). I slightly modified an algorithm I found. I did one or two things to make it look nicer (instead of breaking out of a loop with goto) but those things actually add 2 comparisons (the AND in the while loops) in some cases, so they may slow it down a hair. I suppose I could take them out to see if performance increases. Also, if I wanted to lengthen the script a bit, I could add an insertion sort for segments smaller than 12 items to speed it up further.
Back to the question of whether or not it is "the" quicksort method, hmm. Well, according to the documentation I was reading, the recursive method is called quicksort and the iterative is called qsort.... So, I'm not sure if that was a distinction made by just the author or what, but I'll just call it iterative quicksort. I've looked at several different versions of quicksort, and this one seems to be the best I've found that is not recursive.
Naw.. it wouldn't take you that long:
$a - array
$ls - lower index stack
$us - upper index stack
$sp - stack pointer
$L - lower index
$U - upper index
$i - counter moving from lower index to the right
$j - counter moving from upper index to the left
$p - value of pivot
$t - temp variable for swapping elements
$m - stores either lower or upper index of unsorted segment of the array
If you want to understand the algorithm, it works like this:
1. choose a pivot point
2. swap the elements so that all the elements greater than the pivot are on the right, and all the elements less than are on the left. The pivot point will end up in its correct final position.
3. There will be an unsorted array to the left and right of the pivot, so sort the smaller of the two and put the lower and upper bound of the larger array on the stacks.
4. Continue until each segment is sorted, pulling the lower and upper bound of the unsorted segments of the array off the stack in sequence.
......
There are some nuances to the procedure, but this is the general idea.
Brian
|
|
Top
|
|
|
|
#70355 - 2002-09-27 08:40 PM
Re: Super-quick iterative quicksort!!!
|
NTDOC
Administrator
Registered: 2000-07-28
Posts: 11624
Loc: CA
|
Thanks for the post Brian.
Using this script to read registry data, your script is a little faster on my system.
The CombSort time is: 631 msec
The QS Sort time is: 541 msec
My system has almost 200 software installs on the keys being read into the array.
code:
Break on
$aStart=@ticks
;******************************************
;$software = combsort(getinstalledsoftware)
$software = qs(getinstalledsoftware)
;*******************************************
$aStop=@ticks
? "Running Time is: " $aStop-$aStart
Return
function GetInstalledsoftware
Dim $softwarekey, $index
dim $temparray[10]
$SoftwareKey = enumkey("HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\",$Index)
while not @error
$DisplayName = readvalue("HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\$SoftwareKey","displayname")
$DisplayVersion = readvalue("HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\$SoftwareKey","DisplayVersion")
if $DisplayName
if $count > ubound($temparray)
redim preserve $temparray[ubound($temparray)+10]
endif
$temparray[$count] = $DisplayName +" "+ $DisplayVersion
$count = $count + 1
endif
$Index = $Index + 1
$SoftwareKey = enumkey("HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall\",$Index)
loop
if $count > 0
redim preserve $temparray[$count-1]
else
$temparray = ""
endif
$getinstalledsoftware = $temparray
endfunction
Function CombSort($v, Optional $o)
Dim $i,$j,$m,$s,$g
$n=UBound($v)
$g = $n
If $g
While $g > 1 Or Not $s
$g=($g*1000)/1279
If $g < 1
$g = 1
EndIf
$s=1
For $i = 0 To $n-$g
$j=$i+$g
If ($v[$i] > $v[$j] And Not $o) Or ($v[$i] < $v[$j] And $o)
$m = $v[$i]
$v[$i] = $v[$j]
$v[$j] = $m
$s=0
EndIf
Next
Loop
$CombSort = $v
Else
$CombSort = 0
EndIf
EndFunction
function qs($a)
DIM $ls[32],$us[32],$sp,$L,$U,$m,$p,$i,$j,$t
$ls[0]=0
$us[0]=UBOUND($a)
$sp=0
While $sp >=0
$l=$ls[$sp]
$u=$us[$sp]
While $L < $U
$p=$L+($U-$L)/2
$t=$a[$L]
$A[$L]=$A[$P]
$A[$P]=$t
$i=$L+1
$j=$U
:L1
While ($i<$j) AND $A[$L] > $A[$i]
$i=$i+1
Loop
While ($j>=$i) AND $A[$j] > $A[$L]
$j=$j-1
Loop
IF $i >= $j goto L2 ENDIF
$t=$A[$i]
$A[$i]=$A[$j]
$A[$j]=$t
$j=$j-1
$i=$i+1
Goto L1
:L2
$t=$a[$l]
$a[$l]=$a[$j]
$a[$j]=$t
$m=$j
If $m-$l <= $u - $m
If $m+1 < $u
$ls[$sp]=$m+1
$us[$sp]=$u
$sp=$sp+1
Endif
$u=$m-1
Else
If $m-1 > $l
$ls[$sp]=$l
$us[$sp]=$m-1
$sp=$sp+1
Endif
$l=$m+1
Endif
Loop
$sp=$sp-1
Loop
$qs=$a
Endfunction
|
|
Top
|
|
|
|
|
#70357 - 2002-09-27 09:39 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
I'm glad I could help, doc! After further testing, the modification I made from the original algorithm seems to have sped up the function rather than slow it down:
While $a and $b
Loop
Runs faster than:
While $a
If not $b Goto out endif
Loop
:out
.....
I'm going to see if there are other changes that KiXtart would like.
Brian
|
|
Top
|
|
|
|
#70358 - 2002-09-27 09:50 PM
Re: Super-quick iterative quicksort!!!
|
Chris S.
MM club member
Registered: 2002-03-18
Posts: 2368
Loc: Earth
|
You could change $a to just $ to lower your KiXGolf score, but it probably wouldn't be considered 'best practice.' ![[Big Grin]](images/icons/grin.gif)
|
|
Top
|
|
|
|
|
#70359 - 2002-09-27 10:02 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
Ha! I'm not worried about lowering the score.. I'm looking purely for speed. I'm wondering if smaller variable names would actually speed it up.... I notice that several comparisons are made prior to any elements being "swapped".. I don't really see how I can reduce them....
It would be SO nice to have a "SWAP" command in KiXtart.
Brian
|
|
Top
|
|
|
|
|
#70362 - 2002-09-27 11:12 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
Here is a better description of the code:
Take $array=3,3,6,2,4,6,7,9,2
1. Set pivot to average index of 1st and last element to be sorted:
code:
$p=$L+($U-$L)/2
3,3,6,2,4,6,7,9,2
2. Exchange the pivot value with the lower value:
code:
$t=$a[$L]
$A[$L]=$A[$P]
$A[$P]=$t
4,3,6,2,3,6,7,9,2
3. Leave pivot point alone, and working with the other elements in the set, going from left to right, find a number greater than the pivot value.. working from right to left find a number less than the pivot value.
code:
$i=$L+1
$j=$U
:L1
While ($i<$j) AND $A[$L] > $A[$i]
$i=$i+1
Loop
While ($j>=$i) AND $A[$j] > $A[$L]
$j=$j-1
Loop
4,3,6,2,3,6,7,9,2
4. Swap these numbers.
code:
IF $i >= $j goto L2 ENDIF
$t=$A[$i]
$A[$i]=$A[$j]
$A[$j]=$t
4,3,2,2,3,6,7,9,6
5. Continue to the right to find a larger number than the pivot, and to the left to find a smaller number. Repeat process.
code:
$j=$j-1
$i=$i+1
Goto L1
4,3,2,2,3,6,7,9,6
6. If no other numbers to swap are found, exit loop.
code:
IF $i >= $j goto L2 ENDIF
4,3,2,2,3,6,7,9,6
7. Swap pivot with the location the left and the right converge. Notice that the pivot is sorted and you can now split the array into two sets of numbers.
code:
$t=$a[$l]
$a[$l]=$a[$j]
$a[$j]=$t
3,3,2,2,4,6,7,9,6
8. Set pointer to index where pivot ends up.
code:
$m=$j
In this case $j is 4 so $m is set to 4
9. If set on the left has fewer or the same number of elements as the one on the right, put $m+1 index on the left stack and the right index on the right stack. Set upper index to the element left of the pivot. Otherwise do the reverse.
code:
If $m-$l <= $u - $m
If $m+1 < $u
$ls[$sp]=$m+1
$us[$sp]=$u
$sp=$sp+1
Endif
$u=$m-1
Else
If $m-1 > $l
$ls[$sp]=$l
$us[$sp]=$m-1
$sp=$sp+1
Endif
3,3,2,2,4,6,7,9,6
StackL=5,0,0,0,0,0...
StackU=8,0,0,0,0,0...
Stack pointer changed to 1
Upper element of set = 3
Lower element of set = 0
3,3,2,2,4,6,7,9,6
9. Repeat process from 1 to 7. (loop)
a. swap pivot:
3,3,2,2, 4,[6,7,9,6]
2,3,3,2, 4, [6,7,9,6]
b. swap from greater than pivot from left with less than pivot from right:
2,3,3,2, 4,[6,7,9,6]
2,2,3,3, 4, [6,7,9,6]
-- no change in this case --
c. when right and left converge, swap pivot with convergence.
2,2,3,3, 4, [6,7,9,6]
Because this set is now sorted, no more swaps will take place.
10. The item on the stack is pulled off and the process is repeated until the sort is complete.
code:
While $sp >=0
$l=$ls[$sp]
$u=$us[$sp]
The set 6,7,9,6 is pointed to by the 5 and 8 of the stack pointer
The process is repeated for these:
choose pivot:
[2,2,3,3,4,] 6,7,9,6
find numbers to swap:
[2,2,3,3,4,] 7,6,9,6
[2,2,3,3,4,] 7,6,6,9
swap pivot into place where right and left meet:
[2,2,3,3,4,] 6,6,7,9
11. Sort finished:
2,2,3,3,4,6,6,7,9
Total swaps = 9
This is more efficient with larger data sets
Any questions? (I apologize.. I had pointers showing what numbers were related to what, but i had to delete them because they weren't lining up correctly.)
Brian
[ 27. September 2002, 23:20: Message edited by: BrianTX ]
|
|
Top
|
|
|
|
|
#70363 - 2002-09-27 11:15 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
To Lonkero:
I am using goto.. although I cut it out of a couple places... If you see a more graceful way for me to exit that particular loop, let me know!
Brian
|
|
Top
|
|
|
|
|
#70364 - 2002-09-30 11:02 PM
Re: Super-quick iterative quicksort!!!
|
Lonkero
KiX Master Guru
Registered: 2001-06-05
Posts: 22346
Loc: OK
|
|
|
Top
|
|
|
|
|
#70366 - 2002-09-30 11:52 PM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
Sorting on a single dimension and shuffling the data so that the other dimensions corresponded to the same data as before would be the way to go:
DIM $a[1,1]
$a[0,0]=1
$a[0,1]=0
$a[1,1]=2
$a[1,0]=3
A table:
--------2nd dimension
-------- 0 1
1st---0 1 0
------1 3 2
To sort this, you have to specify which row or column to sort. This causes a problem because there are 4 different ways to sort.
If you have more than 2 dimensions, it gets even dicier because you have to realign all of the other dimensions to the one you sort on.
(Major mindbender!!)
Brian
|
|
Top
|
|
|
|
|
#70368 - 2002-10-01 01:03 AM
Re: Super-quick iterative quicksort!!!
|
BrianTX
Korg Regular
Registered: 2002-04-01
Posts: 895
|
Hmm.. I suppose you could sort any dimension...
If you had:
DIM $a[$x,$y,$z]
You could sort any of the 3 dimensions.. (This would be a 0 index sort, kind of like starting in the corner of a rubik's cube and labelling 0 for each axis.) The problem would be that for each item in the $x dimension that you sort, $y*$z items would have to be moved as well. In addition to that, you might want to sort a different index. Unfortunately, KiXtart will not allow you to operate on a section of the array at a time. You have to assign values for each and every slot.
Brian
|
|
Top
|
|
|
|
Moderator: Glenn Barnas, NTDOC, Arend_, Jochen, Radimus, Allen, ShaneEP, Ruud van Velsen, Mart
|
0 registered
and 369 anonymous users online.
|
|
|
