reduce memory size in quicksort

[Agamemnus]

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%..

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

[Moneo]

Aga, 'ol buddy, couldn't possibly help you without a detailed definition of what you're trying to do. An iterative quicksort is not an easy problem in itself. The only one I've seen uses a stack implemented and controlled by the program.
*****

[Antoni Gual]

Aga:
I had this one from Biskbart, it uses only a pair of auxiliar index arrays:

Code:

SUB fastsort (SortArray() AS sorttype, Lower AS INTEGER, Upper AS INTEGER)
'QuickSort iterative (rather than recursive) by Cornel Huth
'Sorts the part of SortArray between Lower and Upper indexes.

DIM Lstacklo(1 TO 128) AS INTEGER, Lstackhi(1 TO 128) AS INTEGER' stack of indexes to SortArray
DIM Sp AS INTEGER, i AS INTEGER, j AS INTEGER, hi AS INTEGER, lo AS INTEGER
DIM mid AS INTEGER

Sp = 1
Lstacklo(Sp) = Lower
Lstackhi(Sp) = Upper
Sp = Sp + 1
DO
  Sp = Sp - 1
  low = Lstacklo(Sp)
  hi = Lstackhi(Sp)
  DO
   i = low
   j = hi
   mid = (low + hi) \ 2
  'I was comparing z coords, change to fit your needs
  Compare = SortArray(mid).z
  DO
   WHILE SortArray(i).z > Compare: i = i + 1: WEND
   WHILE SortArray(j).z < Compare: j = j - 1: WEND
   IF i <= j THEN
    SWAP SortArray(i), SortArray(j)
    i = i + 1
    j = j - 1
  END IF
LOOP WHILE i <= j
IF j - low < hi - i THEN
  IF i < hi THEN
   Lstacklo(Sp) = i
   Lstackhi(Sp) = hi
   Sp = Sp + 1
  END IF
  hi = j
ELSE
   IF low < j THEN
     Lstacklo(Sp) = low
     Lstackhi(Sp) = j
     Sp = Sp + 1
    END IF
    low = i
   END IF
  LOOP WHILE low < hi
LOOP WHILE Sp <> 1
END SUB

[Agamemnus]

Moneo: it sorts a value and index array pair.

yeah, that works. I'll try it...

EDIT: It sorts great, and uses less complex code than my previous one, but it sorts greatest to least. Anyone got any idea how to fix it?

Code:

DECLARE SUB qsort.linked (array1() AS LONG, array2() AS INTEGER, a.max%)
CLS
RANDOMIZE TIMER
a.max% = 10000
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%

'FOR i% = 1 TO a.max%
'PRINT array1(i%); array2(i%)
'NEXT i%
'PRINT

t1# = TIMER
qsort.linked array1(), array2(), a.max%
t2# = TIMER
PRINT t2# - t1#
SLEEP
'FOR i% = 1 TO a.max%
'PRINT array1(i%)'; array2(i%);
'NEXT i%

SUB qsort.linked (array1() AS LONG, array2() AS INTEGER, a.max%)
DIM g2(1 TO a.max%) AS INTEGER, h2(1 TO a.max%) AS INTEGER, i AS INTEGER, j AS INTEGER, k AS INTEGER, r AS INTEGER, e AS INTEGER, g AS INTEGER, h AS INTEGER
e = 1: g2(1) = 1: h2(1) = a.max%
1 g = g2(e): h = h2(e)
2 i = g: j = h: r = (g + h) \ 2: k = array1(r)
3 IF array1(i) > k THEN i = i + 1: GOTO 3
4 IF array1(j) < k THEN j = j - 1: GOTO 4
IF i <= j THEN SWAP array1(i), array1(j): SWAP array2(i), array2(j): i = i + 1: j = j - 1
IF i <= j THEN GOTO 3
IF j - g + i < h THEN
IF i < h THEN g2(e) = i: h2(e) = h: e = e + 1
h = j
ELSE
IF g < j THEN g2(e) = g: h2(e) = j: e = e + 1
g = i
END IF
IF g < h THEN GOTO 2 ELSE e = e - 1: IF e THEN GOTO 1
END SUB

[Antoni Gual]

At first glance it should work if you reverse the comparisonsin lines 3 and 4...

[Agamemnus]

EDIT:

Yeah, ok, thanks.

If I switch > to < and < to > in 3 and 4, it works.