I thought QB recursion was slower than using arrays.
However now it seems quite the opposite, after some testing.
I tested i%, j%, and k% arrays in my QB recursive quicksort. On a 5000-value array, the speed slows from about 4 to 5 seconds to 7.5 seconds, a speed decrease of 50%!!!
Sorry for confusing some people who saw my earlier post about making a non-recursive quicksort. I deleted it.
Code:
DECLARE SUB do.sort (array1() AS INTEGER, g%, h%)
'initialize an array.
array.max% = 5000: DIM array1(array.max%) AS INTEGER, number AS INTEGER
'generate random numbers.
CLS : RANDOMIZE TIMER: FOR i% = 1 TO array.max%: array1(i%) = INT(RND * 5000) + 1: NEXT i%
'sort the array.
t1 = TIMER
do.sort array1(), 1, array.max%
t1 = TIMER - t1
PRINT the; sorted; array.
PRINT "Final sorted array :": PRINT : FOR i% = 1 TO array.max%: PRINT array1(i%); : NEXT i%
PRINT : PRINT : PRINT t1
SUB do.sort (array1() AS INTEGER, g%, h%)
IF g% >= h% THEN EXIT SUB
IF h% - g% < 1 THEN IF array1(g%) > array1(h%) THEN SWAP array1(g%), array1(h%): EXIT SUB ELSE GOTO 1
1 SWAP array1(h%), array1(INT(RND * (h% - g% + 1)) + g%): k% = array1(h%)
2 i% = g%: j% = h%
3 IF i% < j% AND array1(i%) <= k% THEN i% = i% + 1: GOTO 3
4 IF j% > i% AND array1(j%) >= k% THEN j% = j% - 1: GOTO 4
IF i% < j% THEN SWAP array1(i%), array1(j%): GOTO 2 ELSE SWAP array1(i%), array1(h%)
IF i% + i% - g% < h% THEN do.sort array1(), g%, i% - 1: do.sort array1(), i% + 1, h% ELSE do.sort array1(), i% + 1, h%: do.sort array1(), g%, i% - 1
END SUB
Hmmm... Iterative Quicksort is way faster than the recursive one, at least in therms of big O. Ask loosecaboose. Maybe the conversion was not done correctly, or it was done in not a very efficient manner. I will search for my iterative version and will test... Have you followed all the directions in the recursive->iterative method?
Well all I did was change i, j, and k to an array.... i had i2 = i2 + 1 at the start and i2 = i2 - 1 at the end..
If you find the iterative one and it is better, please post it!
There is a formal method to convert a recursive function into an iterative function. Usually, the iterative version is way faster. Most sollutions use stacks to store values, simulating a recursive call. Here:
http://www.mathcs.carleton.edu/courses/c...lgory.html is a complete article discursing about iterative & recursive quicksorts, complete with source code and full explanations. In the test, iterative quicksort beated the recursive version by a tad.
Iterative being faster as recursive is just a matter of implementation, as you may notice.
Can you post your code?
Quote:Iterative being faster as recursive is just a matter of implementation, as you may notice.
Wait a second, didn't you say..
Quote:Hmmm... Iterative Quicksort is way faster than the recursive one, at least in therms of big O.
My code is exactly the same code as found in that page, as I followed the directions given and got to a very similar algorithm. It is written in LEA, some non-existing language to work on algorithms in paper.
About the two quotes, I don't see what's wrong :???:
:na_th_an:
you say that one is faster than the other and then say it's just a matter of implementation.
But I think iterative IS faster because it doesn't store the line number, right?
well, the
correct and
optimized iterative version is faster than the recursive. I was talking about it was a matter of implementation 'cause your claimed that your iterative version was slower than your recursive version, just that, so not always iterative is faster than recursive
In the link I gave you, the Iterative version is faster 'cause the time needed to make a function call is unexistent. To call a function, you have to push values in the stack, jump (losing the pipeline and such) and then take back those values from stack again. In an iterative sollution, you don't need to expend all that time.