Qbasicnews.com
January 15, 2021, 11:04:48 AM
 Pages: [1]
 Author Topic: reduce memory size in quicksort  (Read 4034 times)
Agamemnus
x/ \z

Posts: 3491

 « on: July 21, 2003, 07:40:32 PM »

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
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
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Moneo
Na_th_an

Posts: 1971

 « Reply #1 on: July 21, 2003, 09:03:03 PM »

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.
*****
 Logged
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #2 on: July 21, 2003, 11:20:59 PM »

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
 Logged

Antoni
Agamemnus
x/ \z

Posts: 3491

 « Reply #3 on: July 22, 2003, 12:08:49 AM »

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
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
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Antoni Gual
Na_th_an

Posts: 1434

 « Reply #4 on: July 22, 2003, 04:34:18 AM »

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

Antoni
Agamemnus
x/ \z

Posts: 3491

 « Reply #5 on: July 22, 2003, 09:10:52 AM »

EDIT:

Yeah, ok, thanks.

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

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
 Pages: [1]