Sorting an array

[quebasic2]

I was reading the faq on quicksort. Would not this be every bit as fast? It does not require the user to enter a start and quit point, it is nicer code, and easier to understand. var is your array:

FOR a = UBOUND(var) TO 0 STEP -1
FOR b = 1 TO UBOUND(var)
IF var(b) > var(a) THEN SWAP var(a), var(b)
NEXT b
NEXT a

I whipped this up in a few seconds.

 

[CubeE101]

HOW ABOUT THIS...

FOR a = UBOUND(var)-1 TO 1 STEP -1
FOR b = 0 TO a
IF var(b) > var(b+1) THEN SWAP var(b), var(b+1)
NEXT b
NEXT a


Have Fun, Be Young... Code BASIC
-Josh Stribling

http://cubee.topcities.com

 

[quebasic2]

Yeah that's better.

 

[Buff1]

qb2, actually it's not.
I put it in sortdemo.bas and it took several seconds longer
than quiksort.
I also had to add the following for loop at the end.
(using base 1)
for a=1 to ubound(var)-1
if var(a)>var(a+1) then
swap var(a),var(a+1)
end if
next a

because the largest value was coming out as the first.
you probably could get away with
swap var(1),var(ubound(var))
at the end.
or var(0) if using base 0.

 

[Buff1]

Que - i was referring to your first post not the
first reply

 

[quebasic2]

Okay, quicksort is faster, but for all practical purposes would not my code be every bit as useful? For most cases, a few seconds will not make that much difference? I ought to try it with max array size, and see how long it takes.

 

[tsh73]

quebasic2 said:

>Okay, quicksort is faster,
you said it,

>but for all practical purposes would not my code be every bit as useful?
That depends on the purpose, indeed.

>For most cases, a few seconds will not make that much difference? I ought to try it with max array size, and see how long it takes.

I think it would not be that long - on a single run - especially because arrays in QBasic limited to 32000 something elements.
BUT.
There could be things there you need it fast. Like, multiple sorting (say, to keep some array sorted after insertion/deletion.)
And you better know that there is a faster way.
And it's nice to have it handy.

 

[CubeE101]

*NOTE also that if you specifically define a & b as integers it WILL run even faster...

QBasic defaults to float / single precision numbers...
Integers run quite a bit faster...

If you are going for speed...
Use one of the following 3 definitions...

1)...
DEFINT A-Z

2)...
DIM A AS INTEGER, B AS INTEGER

3)...
For A% = 1 to ...
array(A%) = ....

I suggest the second, it is a very good practice if you plan to move on to VB later on... the first is okay, but EVERYTHING will default to integers... the 3rd works too, but requires more typing (that is one of my pet-pieves... ;-))

Good Luck

Have Fun, Be Young... Code BASIC
-Josh Stribling

http://cubee.topcities.com

 

[CubeE101]

Oh...
One other trick is to not sort anything you don't have to...

DIM DONE as Integer, A as Integer, B as Integer, MAX as Integer
MAX = UBOUND(array)-1
DO
  DONE = 1
  B = MAX
  FOR A = 0 TO B
    IF var(b) > var(b+1) THEN
      MAX = A - 1
      DONE = 0
      SWAP var(b), var(b+1)
    END IF
  NEXT 
LOOP UNTIL DONE OR MAX < 1

This will drag the highest number to the top...
Then Mark the point right before the last one changed (MAX)...
The next loop will only go up to the MAX number previosly marked...
When A change is Made, the loop is marked incomplete...
When there are no more changes to be made, the loop will end...

This "should" be one of the fastest searches...
If you find a better one please post it ;-)

If you have an array of 255 elements... and only 1 change to make... it will only run through 1 or 2 times...

if the array is sorted backwards... it will run just like my previous post where the MAX is decreased by 1 each time...

Those are your 2 extreme senarios...

Good Luck and Have FUN ;-)

Have Fun, Be Young... Code BASIC
-Josh Stribling

http://cubee.topcities.com

 

[Buff1]

Cube, It's not. It's basically a bubble sort. It's ok
but not near as fast as QuikSort.

Buff

 

[Cykadelyxx]

qb your algorithim is called a selection sort invented over a half century ago which has an algorithmic complexity of n^2, quicksort is a very good algorithm because it is n*log n .... so the difference is major for large arrays... for an of 1024 quicksort needs 10000 iterations where yours needs over a million. yes it is usually much easier to just write a selection sort then paste a quicksort into your program and I don't think it is considered to be bad programming for small arrays..

 

[logiclrd]

Here is some information on the QuickSort, in case anybody is still a bit confused:

faq314-336 "What is the Quick Sort, and how fast is it, really?"

 

[Dilyias]

I'd say quicksort is the best bet. I wrote a quicksort function in QB that was faster than the bubble sort in directqb (asm). I used it in a 3d engine and it didn't even drop the FPS at all.