Sorting Arrays

[Agamemnus]

Code:

DECLARE SUB qsort.byte.lowstart (array1() AS LONGINT, a.max%)

DIM test1(1 TO 3000000) AS LONGINT
FOR j%  = 1 TO 1

FOR i& = 1 TO 3000000
test1(i&) = INT(RND * 72057594037927936 )
NEXT i&
timerstart# = TIMER
qsort.byte.lowstart test1(), 3000000
timerend# = TIMER
PRINT timerend# - timerstart#
SLEEP
NEXT j%

SUB qsort.byte.lowstart (array1() AS LONGINT, a.max%)
DIM g2(1 TO a.max%) AS INTEGER, h2(1 TO a.max%) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, r AS INTEGER
DIM E AS INTEGER, g AS INTEGER, h AS INTEGER
DIM k AS LONGINT
E = 1: g2(1) = 1: h2(1) = a.max%
f1: g = g2(E): h = h2(E)
f2: i = g: j = h: r = (g + h) \ 2: k = array1(r)
f3: IF array1(i) < k THEN i = i + 1: GOTO f3
f4: IF array1(j) > k THEN j = j - 1: GOTO f4
IF i <= j THEN SWAP array1(i), array1(j): i = i + 1: j = j - 1: IF i <= j THEN GOTO f3
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 f2 ELSE E = E - 1: IF E THEN GOTO f1
ERASE g2, h2
END SUB

[DrV]

Aaaahhh!1 Run away!

jk, good to see you and your algorithms again.

[Anonymous]

takes like 25 seconds on my 500 mhz

[Agamemnus]

which one?

Thank you, DrV.

I'll be adding a function to search sorted arrays in log(n) time tomorrow, hopefully.

[Agamemnus]

Ok.... what I did uses 1 byte not 7. Now I used the 64 bit unsigned integers. (editing the post now) The speed is still 1 second to do the sort as opposed to 7.5 with that first program in powerbasic.

[Anonymous]

unless you have a 64-bit processor, i dont think youll get a speed increase with longint... try making them all integers instead (32-bit)

[Agamemnus]

If you read the first post, he said 7 bytes. That's 56 bits. You can't use a single 32 bit integer for that.

[wallace]

Time and time again a Radix sort will beat a Quicksort when it comes to speed, they usually use LinkedLists, but could be done in FB with simple arrays. I plan to implement one when sorting sprites in the Inspiration Engine.

[dumbledore]

maybe, but crt's qsort was written in c with an optimizing compiler, it'll probably beat you every time ;P

[DrV]

Actually, I think MS's CRT is mostly written in x86 ASM... the sources are distributed with some versions of Visual Studio. (Of course, you can't use them yourself, but they're there for reference.)