+- Qbasicnews.com (http://qbasicnews.com/newforum)
+-- Forum: Qbasic "like" compilers/interpreters (http://qbasicnews.com/newforum/forum-5.html)
+--- Forum: FB Discussion & Programming Help (http://qbasicnews.com/newforum/forum-15.html)
+--- Thread: Sorting Arrays (/thread-6749.html)
Sorting Arrays - Agamemnus - 06-03-2005
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 SUBSorting Arrays - DrV - 06-04-2005
Aaaahhh!1 Run away!
jk, good to see you and your algorithms again.
Sorting Arrays - Anonymous - 06-04-2005
takes like 25 seconds on my 500 mhz
Sorting Arrays - Agamemnus - 06-05-2005
which one?
Thank you, DrV.
I'll be adding a function to search sorted arrays in log(n) time tomorrow, hopefully.
Sorting Arrays - Agamemnus - 06-05-2005
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.
Sorting Arrays - Anonymous - 06-05-2005
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)
Sorting Arrays - Agamemnus - 06-05-2005
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.
Sorting Arrays - wallace - 06-07-2005
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.
Sorting Arrays - dumbledore - 06-07-2005
maybe, but crt's qsort was written in c with an optimizing compiler, it'll probably beat you every time ;P
Sorting Arrays - DrV - 06-07-2005
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.)