Sorting.....

[Neo]

Yeah, it comes with Insertion, Bubble, Exchange, Shell, Quick and Heap sort algorithms.

[Moneo]

Neo, how come you're so sharp, but only 17 years old. You must have started programming in your crib with a laptop.
*****

[Lithium]

I never really used any sort method other than BUBBLE.. most people seem to think this is the best way to do a bubble sort:

Code:

for (i=0; i<array_size; i++)
  for(j=0; j<array_size; j++)
    (whatever);

but this is quicker:

Code:

for (i=0; i<array_size-1; i++)
  for (j=i+1; j<array_size; j++)
    (whatever);

because it eliminates all doubles

so instead of the time to sort being O(N^2)
it's O((N*N-N)/2)[/code]

[oracle]

Just do a merge or quicksort. O(n log(n)).

[Neo]

Neo, how come you're so sharp, but only 17 years old. You must have started programming in your crib with a laptop.
*****

Well, thanks for the compliment
Actually, I started programming when I was 8 years old, but I only started to make some progress in programming when I was 13 years old. So, effectively, I'm programming for almost 5 whole years now. (Which isn't much, compared to e.g. you )
But the real sharpness is simply in me. I'm very strange, mentally seen. And I'm also proud of it to be somewhat different than most other people E.g. I can "control" my mind to some extent, when I want it.
I also reached university level (highest possible education in the Netherlands) on age 16 Which is rare here. In fact, I'm in quite some trouble with some companies because they only have rules for people of 18 years and older. And then I get there... like "I'd like to order insurance, at age 17", which is pretty hard Also, it can be a hassle with filling out forms, because according to the Dutch law, at age 17 and younger, the parents have to sign every form the children sign as well, even with "normal" forms. And I live 300 km away from my parents, on my own, so asking your parents to fill out a form can take very long...

[ToohTooh]

Oz: I remember that Microsoft already compiled a great collection of sorting routines (comparing them) in the QuickBasic 4.5 release.

As far as I remember, heap sorting was implemented beautifully... And, it was my favorite...

Some toughts...

[Oz]

Unfortunately, im looking for speed, not beauty/easy implementation

For all those who aren't aware, this will be for the very nice looking 3d suite im programming (just makes ur mouth water by hearing about it :wink: )

as soon as i can get this implemented, i can start doing some major work

Oz~

[oracle]

Well, like we said, you can get a merge or quicksort algo from the SORTDEMO.BAS file included with the QB distribution

[Oz]

are mergesort and quicksort the same?

Oz~

[oracle]

No.

Mergesort works vaguel like this: Given a list, split it in two, mergesort the first half, mergesort the second half, then mergesort the result. So it's recursive. Splitting the list takes almost no time - if it's an array, you simply make two new arrays, one with indices 0 to size / 2 and the other with the other half. The trickiness is with the merging (although it's not that bad): Simply go down each list, pulling the smallest item from both lists into the result list until both lists are empty.

Quicksort is different: all the work is done in the splitting. It uses an algorithm that "partitions" the incoming array into three parts based on an incoming value, such that all items in the array lower than the incoming value are in lower indices than the value, which is smaller than all the values in the upper part of the array (note that the parts won't be sorted necessarily - all that is guaranteed is that all the values lower than the partition will be before it and vice versa). Then the quicksort algorithm is simply to partition the array, quicksort both halves, then return the merged result (merging is easy - simply quicksorting both halves of the partitioned array means that it's in order.

The reason why quicksort may end up a lot slower is because you could continually pick a bad value for the partition to use. Generally, there are several strategies used:

*) Pick the value that just happens to be in the middle of the array
*) Pick the first or last value
*) Pick three values and choose the middle one
*) ...

However, none of these guarantees that you'll always pick a value such that there is an equal number of values lower or higher than it. So if you kept picking a bad value, the routine could blow out to O(n^2).

Having said that, the chances of this are quite low.