Sorting numbers..
Blitz3D Forums/Blitz3D Beginners Area/Sorting numbers..
| ||
| Hi all, been away for a while but now im back :-) Ok, so im trying to write a piece of code that will organise numbers from highest to lowest. When I used to use "amos" (back in the day) there was a command called Sort which was very easy to use. Can anyone offer some suggestions on the best way to sort stuff! At the moment i can only see my comparing each and every number (which is going to be a massive piece of code considering i need to sort 80 odd numbers!!!!) Thanks in advance |
| ||
Look up bubble sort routines, they're really not big at all, just a couple of nested loops.Graphics 640,480 Dim source(19) Dim sorted(19) For n=0 To 19 source(n)=Rand(1,100) Text 0,(n+1)*20,source(n) Next Text 0,0,"Original List" ; bubble sort For n=0 To 19 For n1=19 To 0 Step-1 If source(n)>sorted(n1) Then nn1=n1 Next n1=nn1 For n2=19 To n1 Step-1 sorted(n2+1)=sorted(n2) Next sorted(n1)=source(n) Next For n=0 To 19 Text 200,(n+1)*20,sorted(n) Next Text 200,0,"Sorted List" WaitKey() |
| ||
| Argh Rob ! You have been faster !!!! Anyway. this link can be useful: http://www.blitzbasic.com/bbs/posts.php?topic=21306 I wrote the bubble sort example for string sorting, but it's easy to convert it for number sorting. Sergio. |
| ||
| The Bubble Sort is one of the easiest programs to write, but it is not especially fast, as it involves more compares and moves over a shorter distance within an array than some other sort methods do. For just 80 numbers, the difference is insignificant. But when you get into the thousands, the difference compounds and becomes very noticable. A much faster method is the QuickSort algorythm, which you can find on the Internet. It isn't the absolute fastest. butg it very fast and has a distinct advantage that it it retains the prior sort order where possible, so if you had separate sorts to do for Last Name, First Name, Middle Initial, etc., you just start with the lowest priority sort and work your way up to the highest priority sort. If you like the Bubble Sort approach, there is a good way to make it faster: Replace the inner loop with a binary search approach, trying to find the right place to insert the out-of-place variable in the quickest time. Whether you can then move all entries en-mass or one-at-a-time, you still have cut the number of compares to a very few, which will make that method more effective. What you are doing in this way is to take advantage that the outer loop has already determined that the lower portion of the array is in correct sequence, so a binary search method can properly be used in place of the inner loop. The bubble-binary approach is particularly good when you are trying to sort records in a file that are all of a given size. If you find this more than you are interested in, I might suggest that you just start with a QuickSort approach. The rest can be explored when you find a need for it. |
   |