Qbasicnews.com
August 09, 2020, 10:53:39 AM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: reduce memory size in quicksort  (Read 3816 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? Smiley

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



WWW
« 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
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
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



WWW
« 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]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!