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

[kc]

I have 2 links for the quick sort algorithms, but they seem to only work with one dimensional array.


http://www.tek-tips.com/gfaqs.cfm/lev2/4...14/fid/336 (better codes, at least shorter)
http://members.lycos.co.uk/brisray/qbasic/qchance.htm

Thanks
kc

[Antoni Gual]

Must all items in a row be bigger (or smaller) than those in the following row?

In other words:
How is your array ordered?

[Neo]

You can't sort a multidimensional array directly. You have to make rules like in which way it must be ordered.

E.g. you have this matrix:

Code:

1085
0582
4759
4185

Do you want it to be sorted to:

Code:

0158
0258
4579
1458

Or to:

Code:

0011
2445
5557
8889

Just say how you want to sort a multidimensional array

[Agamemnus]

http://www.geocities.com/pisforpi/qsort.zip

...pass the array in several times....

or, just change the array to one-dimensional and then back...

[kc]

eg.

kenny 12
steve 8
jenny 10

and sort into

steve 8
jenny 10
kenny 12

or

kenny 12
jenny 10
steve 8


Thanks
kc

[Antoni Gual]

Well, that's not a multi-dimensional array. It's just an one-dimensional array of records or it's two related uni-dimensional arrays (one for strings, one for integers, depending on how you choose to implement it.

QuickSort can be adapted easily to do this. QS performs some comparisons on elements of one array until a condition is true, then SWAPS a couple of elements.

To adapt it to your case you must modify the sources so the comparisons are made in the numeric array and the swaps on both the numeric and the string arrays.
I can't write example code until tonight, I'm sure one of the other posters will do it before me...

[Agamemnus]

It's already in my quicksort list.

All the .linked subs do almost what you want, except the second array (called an ID or index array) is an INTEGER array. I'm sure you could modify it to suit your needs...

[Antoni Gual]

Well, I see no one did it, so there is the code:

Code:

DECLARE SUB quicksort (min%, max%)
DECLARE SUB display ()
DIM SHARED a$(10), b(10)

FOR i% = 0 TO 10: READ a$(i%), b(i%): NEXT
PRINT "initial array"
display
  quicksort 0, 10
PRINT "sorted array"
display
END

DATA "aaa",10,"bbb",37,"ccc",4,"ddd",7,"eee",10
DATA "fff",1,"ggg",12,"hhh",3,"iii",8,"jjj",4,"kkk",-1

SUB display
FOR i% = 0 TO 10
  PRINT a$(i%), b(i%)
NEXT
END SUB

SUB quicksort (min%, max%)
IF min% < max% THEN
    p1% = min%
    p2% = max%
    mid = b((min% + max%) \ 2)    '**
    DO UNTIL p1% > p2%
        DO WHILE b(p1%) > mid      '**<<invert this unequality to sort ascending
            p1% = p1% + 1
        LOOP
        DO WHILE mid > b(p2%)      '**<<this one too
            p2% = p2% - 1
        LOOP
        IF p1% <= p2% THEN
            SWAP a$(p1%), a$(p2%) '**
            SWAP b(p1%), b(p2%)     '**
            p1% = p1% + 1
            p2% = p2% - 1
        END IF
    LOOP
    IF min% < p2% THEN quicksort min%, p2%
    IF p1% < max% THEN quicksort p1%, max%
END IF
END SUB

The lines in the quicksort routine marked with ** are those you must adapt to your data...

If you have a small array e.g. 50 entries, a simpler algorithm, as bubble sort will do it as well. The speed of quicksort makes a difference with big amounts of data.

http://www.geocities.com/pisforpi/qsort.zip

Good work!! :o Just a little puzzling for a newbie, so I posted mine also.

[kc]

Thanks

[Agamemnus]

RECURSIVE!

ARGH!

***MELTS***