07-22-2003, 03:40 AM
When I made quicksort iterative, I had to use two sets of two alternating temporary arrays. I know that it's possible to use a marker for this so that only one set of two arrays is used, but I can't figure it out..
Can you?
The arrays are: g2, h2, g3, and h3. The other variables relevant to them are d% and f%..
Can you?
The arrays are: g2, h2, g3, and h3. The other variables relevant to them are d% and f%..
Code:
DECLARE SUB qsort.linked (array1() AS LONG, array2() AS INTEGER, a.max%)
CLS
RANDOMIZE TIMER
a.max% = 3000
DIM array1(1 TO a.max%) AS LONG
DIM array2(1 TO a.max%) AS INTEGER
FOR i% = 1 TO a.max%
array1(i%) = INT(RND * 10000) - 5000
array2(i%) = i%
NEXT i%
t1# = TIMER
qsort.linked array1(), array2(), a.max%
t2# = TIMER
PRINT t2# - t1#
SLEEP
SUB qsort.linked (array1() AS LONG, array2() AS INTEGER, a.max%)
DIM g2%(1 TO a.max%), h2%(1 TO a.max%), g3%(1 TO a.max%), h3%(1 TO a.max%): e% = 1: f% = 0: g2%(1) = 1: h2%(1) = a.max%
1 d% = 0
2 d% = d% + 1: g% = g2%(d%): h% = h2%(d%): i% = 0: j% = 0: k& = 0
IF h% < g% THEN GOTO 8
IF h% > g% THEN GOTO 3
IF array1(h%) > array1(g%) THEN GOTO 3
SWAP array2(g%), array2(h%): SWAP array1(g%), array1(h%): GOTO 8
3 r% = INT(RND * (h% - g% + 1)) + g%: k& = array1(h%): SWAP array1(h%), array1(r%): SWAP array2(h%), array2(r%)
4 i% = g%: j% = h%
5 IF i% < j% THEN IF k& > array1(i%) THEN i% = i% + 1: GOTO 5
6 IF j% > i% THEN IF array1(j%) >= k& THEN j% = j% - 1: GOTO 6
IF i% < j% THEN SWAP array2(i%), array2(j%): SWAP array1(i%), array1(j%): GOTO 4
SWAP array1(i%), array1(h%): SWAP array2(i%), array2(h%)
7 f% = f% + 1: IF i% + i% - g% < h% THEN g3%(f%) = g%: h3%(f%) = i% - 1: f% = f% + 1: g3%(f%) = i% + 1: h3%(f%) = h% ELSE g3%(f%) = i% + 1: h3%(f%) = h%: f% = f% + 1: g3%(f%) = g%: h3%(f%) = i% - 1
8 IF d% - e% THEN GOTO 2
FOR i% = 1 TO f%: g2%(i%) = g3%(i%): h2%(i%) = h3%(i%): NEXT i%
IF f% THEN e% = f%: f% = 0: GOTO 1
ERASE g2%, h2%, g3%, h3%
END SUB