How do I sort arrays?

DavidM

HI,

I need to read from an array of numbers ( LONGS) in ascending order, the array has numbers in a random order originally , but I need to read them from smallest to largest.

Any Ideas?


Thanks


dave M

Timmoore

Theres lot of ways to do this, depending on size of array, amount of spare ram, etc. but I would probably start with http://obex.parallax.com/objects/306/ since it already exists.

DavidM

Thanks I will have a look


Dave M

J. A. Streich

Merge sort and Qucik Sort can be done in place. Merge Sort takes O(n log n) in all cases, Quick Sort takes best case: O(n log n) worst case O(n^2), but uses less resources.
Selection sort probably takes the lest resources and is the easiest to implement; but it runs in O(n^2).

DavidM

HI Striech,

I have no idea of what you are talking about?

Can you give some examples of sorting?

thanks

Dave M

Mike Green

The Wikipedia has lots of articles on sorting. Do a web search for "wiki quicksort", "wiki heapsort", and "wiki merge sort".

rokicki

Shell sort is an interesting sort for its simplicity and immunity to bad cases.
For the number of values you'd be able to store in the propeller, it's unlikely
to be significantly slower than any other algorithm.

Wikipedia has articles on the common sort algorithms, such as

http://en.wikipedia.org/wiki/Shell_sort

I'd start there.

If you do use Shell sort, use a reasonable gap sequence and not just the
stupid arraysize/2 and down that many people use. See:

http://www.research.att.com/~njas/sequences/A102549

It would be kind of neat to make this into a contest and see how fast people
can get the Prop to sort (in Spin) vs code size.

rokicki

If you have fewer than about 100 numbers, a trivial insertion sort will do fine, by the way.

Rayman

This reminded me of the QBasic sort routines from long ago...· I seem to recall that bubble sort was the fastest...

http://www.network54.com/Forum/182035/message/1080871119/Sort+Demo+that+came+with+original+QB4.5+disks

Might be fun for someone to convert to Spin...

·

DavidM

HI, Those wiki pages have some interesting reading,
I was thinking along the lines of creating an INDEX array as I actually have 3 arrays ( of the same size about 32 LONGS each so its is small) that need to be sorted, so instead of sorting the 3 arrays, I create a new array of the same size and place the sort order index values in that, then I can refer to the other tree arrays as needed.

By the way I do have DATABASE programming skills ( 4D and SQL ) but indexing is usually done automatically when records are created,

so maybe another approach is to create the SORT index while the data for the arrays is being created, this may save some LOOP time. I do need to sort as quickly as possible.

what do you think

By the way, that SPIN sorting object appaers to workk on having an axtra array for the sort, ( called sister array) by the documentation says it does not require another array, a little confused.

Dave M

rokicki

For 32 values, just use insertion sort. *Maybe* a single prepass with an increment of something like 7 might help, but insertion sort will be fine.

Note, *not* bubble sort. Insertion sort.

DavidM

Thanks for suggestions..

After looking at my code I do not want to change the real order of any of the longs in my three arrays, I would really just like to create an INDEX ARRAY. That way, when I need to read the values from my 3 arrays I will use the INDEX ARRAY for indexing,

So I need some kind of guidance into how to read the values of the array to sort and put its "SORT ORDER" into a new INDEX ARRAY, I had a look at the wiki pages but got a headache:-(

Thanks

dave M