For 10 words, a simple bubble sort should suffice. I've never programmed in PBasic though, so I don't know what it does and does not support. It basically keeps iterating through the list, swapping ajacent elements, and stops when it does a complete iteration without swapping any elements.
There are many other methods you can use too. Like I said, I've never programmed in PBasic (yet, should have my stamp ready tonight), and I program mainly in Java and C/C++, but you can also look into QuickSort and Merge Sort. Quick Sort, when utilized correctly, can be FAST. I managed to write a QuickSort class in Java that sorter 100,000 wordes in less than a second, though that was using doubly linked lists and a couple other methods I'm sure PBasic doesn't support. But look into them, with just 10 words though, Bubble Sort won't slow you down any.
The attached program has a bubble sort subroutine. I embedded it in a simulated game with 11 players, so that after each player's turn, the program calls the bubble routine to rank the scores. You enter a score (0-65535) at the keyboard and the demo displays the results of the sort. I hope the comments make clear what is going on. (The number of players is a compile time constant.)
This runs on Stamps with scratchpad RAM, as that is where the ranks and scores are stored. There are two tables in spRAM. The ranks table is 11 bytes and the scores table is 11 words, one rank and one score for each player. The scores stay in sequential order of play, while it is the ranks are sorted. The ranks are pointers to the corresponding score.
I've used this in data acquisition, where it helps with non-parametric filtering and statistics, like the median and quartiles.
You raise an interesting point by mentioning medians. There are shortcuts for computing the median that don't require a complete sort. Have you tried any of them in PBASIC or know if any of them are realistically feasible with a Stamp?
Did you have something like the divide and conquer algorithm in mind? I haven't dug into it, but the theory says that can work in O(n) whereas the standard algorithm works in O(n log n). I had a demo from some programming language I don't remember that would illustrate the speed of different algorithms working on sample lists, and it even had cute sound effects. As AltarCrystal pointed out, some algorithms have truely astounding speed in comparison the bubble sort.
However, a lot can depend on the state of the list at the start. In the example the sort is done after each player, or after each new data point replaces the oldest one. The list is already sorted except for the new entry. The bubble algorithm as written terminates when there are no more swaps, so it runs much faster than if you throw a whole new set of random numbers at it. However, there is no doubt a faster algorithm for the former situation too; an initial binary search through the ranking should be able to locate quickly the position of the new entry. Something to think about for longer data sets.
StuartW
Posts: 3
Comments
For 10 words, a simple bubble sort should suffice. I've never programmed in PBasic though, so I don't know what it does and does not support. It basically keeps iterating through the list, swapping ajacent elements, and stops when it does a complete iteration without swapping any elements.
http://en.wikipedia.org/wiki/Bubble_sort
There are many other methods you can use too. Like I said, I've never programmed in PBasic (yet, should have my stamp ready tonight), and I program mainly in Java and C/C++, but you can also look into QuickSort and Merge Sort. Quick Sort, when utilized correctly, can be FAST. I managed to write a QuickSort class in Java that sorter 100,000 wordes in less than a second, though that was using doubly linked lists and a couple other methods I'm sure PBasic doesn't support. But look into them, with just 10 words though, Bubble Sort won't slow you down any.
This runs on Stamps with scratchpad RAM, as that is where the ranks and scores are stored. There are two tables in spRAM. The ranks table is 11 bytes and the scores table is 11 words, one rank and one score for each player. The scores stay in sequential order of play, while it is the ranks are sorted. The ranks are pointers to the corresponding score.
I've used this in data acquisition, where it helps with non-parametric filtering and statistics, like the median and quartiles.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
You raise an interesting point by mentioning medians. There are shortcuts for computing the median that don't require a complete sort. Have you tried any of them in PBASIC or know if any of them are realistically feasible with a Stamp?
-Phil
Did you have something like the divide and conquer algorithm in mind? I haven't dug into it, but the theory says that can work in O(n) whereas the standard algorithm works in O(n log n). I had a demo from some programming language I don't remember that would illustrate the speed of different algorithms working on sample lists, and it even had cute sound effects. As AltarCrystal pointed out, some algorithms have truely astounding speed in comparison the bubble sort.
However, a lot can depend on the state of the list at the start. In the example the sort is done after each player, or after each new data point replaces the oldest one. The list is already sorted except for the new entry. The bubble algorithm as written terminates when there are no more swaps, so it runs much faster than if you throw a whole new set of random numbers at it. However, there is no doubt a faster algorithm for the former situation too; an initial binary search through the ranking should be able to locate quickly the position of the new entry. Something to think about for longer data sets.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com
I've started a new thread regarding medians here, so as not to hijack this one.
-Phil