Can I use QuickSort on multi-dimensional arrays? Please help

[kc]

Agamemnus,

Sorry, I am a Newbie, I am just using Qbasic to accomplish one task only, I am not a programmer. That is why I sometimes makes these stupid mistakes or questions. So what is wrong with "RECURSIVE" routine?

BTW thnaks for your help, your Qsort.bas is little puzzling, but one of these days I will go thru it.

kc

[toonski84]

Recursive in qb:
for some reason, qb eats up stackspace like a starving fat man. I've gotten so many "out of stack space" errors from using recursion, I find it best just to use nonrecursive routines.

[Antoni Gual]

This one will eat only 12 bytes in variables per call. How big is the default QB stack? I don't have the manual....

You could make the variable mid STATIC, this would reduce the stack use to 8 bytes . And if you run out of stack you coud use CLEAR,,8000 at the start of the program.

With the maximum array index limits of QB, you will not have problems with this routine. I have used it to sort 2000 triangles in a 3d program.

EDITED:
This test gives a maximum recursion depth of 34 and a stack use of 720 bytes, and i had to add a new parameter (eating more stack) to keep track of recursion depth. Without the additional parameter the stack use is below 600 bytes.

Code:

DECLARE SUB quicksort (min%, max%, n%)
REDIM SHARED b(-16367 TO 16367), c(-16367 TO 16367)
RANDOMIZE TIMER
DIM SHARED stack%, cnt%
stack% = 32767
stack0% = FRE(-2)
PRINT "initial stack"; stack0%
FOR i% = -16367 TO 16367: b(i%) = RND: c(i%) = b(i%): NEXT
PRINT "sorting"
quicksort -16367, 16367, 1
PRINT "minimum stack"; stack%
PRINT "stack use"; stack0% - stack%
PRINT "max depth"; cnt%
END

SUB quicksort (min%, max%, n%)
STATIC mid
IF FRE(-2) < stack% THEN stack% = FRE(-2)
IF cnt% < n% THEN cnt% = n%
IF min% < max% THEN
    p1% = min%
    p2% = max%
    mid = b((min% + max%) \ 2)
    DO UNTIL p1% > p2%
        DO WHILE b(p1%) > mid
            p1% = p1% + 1
        LOOP
        DO WHILE mid > b(p2%)
            p2% = p2% - 1
        LOOP
        IF p1% <= p2% THEN
            SWAP b(p1%), b(p2%)
            SWAP c(p1%), c(p2%)
            p1% = p1% + 1
            p2% = p2% - 1
        END IF
    LOOP
    IF min% < p2% THEN quicksort min%, p2%, n% + 1
    IF p1% < max% THEN quicksort p1%, max%, n% + 1
END IF
END SUB

[kc]

Thanks to all.

Especially to Antoni Gual for your time writing the codes for me. Althought What I intend to do is a little more complicated that what I have asked, but I will try to figure it out myself, if I still can't do myself, hopefully someone here can help.

Specifically this is what I need.

I have a multi-dimensional arry in the form of :
DIM data (1000, 10) as SINGLE ' 1,000 rows and 10 columns

Sort this based on 1 of the 10 columns.
If the array is too big to fit into local memory, can I perform the sort from a Random Access file?

Once again, thank you so much.
kc

[Antoni Gual]

If you use REDIM instead of DIM you will be ok with your array and with much bigger ones