 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Sorting data
Page 1 of 2   |
|||||
| Author | Message | ||||
| factus10 Regular Member  Joined: 30/12/2014 Location: United StatesPosts: 45 |
Hi all, I'm brand new here but very excited about my new Circuit Gizmo's ColorMax 2. A comment about the relatively slow speed of the bubble sort in the MM library prompted me to jump back into GW-style BASIC. I tried to implement a quicksort in MM Basic before I came across the comment about not being able to pass arrays to subroutines... so, that was out. I did some digging and implemented a Shell sort, comb sort and bubble sort in MM Basic, in both numeric and string versions. My code is below. There's enough random string data that you can test it for arrays up to 1000 elements. Anyway, here are the results of running it on array sizes of 100, 250, 500 and 1000 elements are (in timer ticks): Numeric sort 100 250 500 1000 Shell 16 62 203 499 Comb 15 31 197 281 Bubble 78 546 2387 11403 String (alpha) sort 100 250 500 1000 Shell 31 110 281 811 Comb 16 46 125 344 Bubble 78 858 4539 27674 Here's the code (zipped b/c of the largish data set) 2014-12-31_042101_selectionsort.zip Best, David |
||||
| matherp Guru  Joined: 11/12/2012 Location: United KingdomPosts: 10565 |
David Thanks for the very useful code. MMBasic on the Micromite MKII now supports arrays passing to subroutines (see the MM manual). It would be very interesting to see results of your quicksort on that. If you want to blind code it I could run it for you. best regards Peter |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Hi Peter, Thanks for the heads-up. That'll be fantastic. I'm looking at updating my ColorMax2 in a few minutes but first, I thought I'd run the code on it for some data. Here's how the sorts I've coded thus far performs on MMBasic 4.5: [code] Numeric sort 100 250 Shell 918 2182 Comb 485 1457 Bubble 2926 19484 String (alpha) sort 100 250 Shell 994 3222 Comb 481 1656 Bubble 4009 34585 [/code] There's not enough memory to run the code w/ 500 elements (mainly b/c I've dimensioned 4 arrays of 500 elements... you could prob do it w/ one array). Once I update to 4.6, I'll add Quicksort. PS. Forgot to mention in my original post: those numbers are for the DOS version of MMBasic. I just this morning managed to connect to my ColorMax from my computer. |
||||
twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
Hi David, thanks a lot for this code! I tried in the past Bubble sort and Heap sort and I could not get acceptable results. With Comb sort I now get 10 times better performance compared with Bubble sort. That's very useful for my File Selector for Maximites! 
Regards Michael edit: Thats explains why I got slower results on my Duinomite.  causality ≠ correlation ≠ coincidence |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Err, whoops. I misunderstood about the update to Micromite basic. It doesn't work on my Colormax. Do we know if/when the DOS version will be updated to 4.6? |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
I think Geoff will know. More important seems to me a update for Maximites. This would reanimate the Maximites. I think it deserves it! Michael causality ≠ correlation ≠ coincidence |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Yes, updates to the Maximites would be fantastic, too :) |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Michael, It was your comment about the bblsort in your filemanager that got me started. 20+ years ago, I did a lot of quickbasic programming and at the time, quicksort was the best I knew about, so it was my first thought. I wanted to make sure I coded it in a way that you could use it. I've learned a few things about sorts in the past few days. I'm pretty happy with comb sort performance in 4.5 so far. Best, David |
||||
Justplayin Guru Joined: 31/01/2014 Location: United StatesPosts: 330 |
If you need more memory a Maximite (color or mono version) and don't need to use the VGA display output, try CONFIG VIDEO OFF (reboot required). That will release the video memory so it can be used for your own code. With the video off you will have close to 100K of free memory to use. --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Thanks :) I don't I think I have the patience to wait for a bubble sort on more than 250 items, though. |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
Hi factus10, That's what you did. Good job! 
I thought I would have to write bblsort as cfunction. The new version of FS (Fileselector /FileManager) is already available.  Happy 2015 to all TBS members!
Michael causality ≠ correlation ≠ coincidence |
||||
| shoebuckle Senior Member  Joined: 21/01/2012 Location: AustraliaPosts: 189 |
Out of curiosity, I thought I would try a Cocktail Sort which is the same as a bubble sort except that it searches alternately up and down the list. The results using DOS MMBasic 4.5 under Win7 on my laptop were: Array size 1000 ---------------- nShellSort 281 nCombSort 140 nCocktailSort 4633 nBubbleSort 6037 --------------- String Arrays ---------------- aShellSort 406 aCombSort 172 aCocktailSort 6162 aBubbleSort 15148 --------------- The code I tried for the nCocktailSort is sub nCocktailSort(j)
' Sames a bubble sort except that on alternate passes ' it sorts last to first Flips = 1 Do Flips = 0 'Scan from first to last For n=1 To j-1 If mArnum(n) > mArnum(n+1) Then SWAP mArnum(n),mArnum(n+1) Flips = 1 EndIf Next if Flips=1 then Flips = 0 'Scan from last to first For n=j-1 To 1 step -1 If mArnum(n) > mArnum(n+1) Then SWAP mArnum(n),mArnum(n+1) Flips = 1 EndIf Next Endif Loop While Flips = 1 end sub I am not suggesting you use the cocktail sort, especially as the size of the code is almost the same as the Shell- and Comb-Sorts. This was just an exercise to see what the difference was. Cheers, Hugh |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
Hi Hugh, it's always useful to have a choice and one can compare. I was absolutely amazed about David's Comb Sort performance. I would be greatly appreciated to have Daniels (and your) code in the MMBasic library. Maybe my recently released code examples will find a way to get there? Regards Michael causality ≠ correlation ≠ coincidence |
||||
| shoebuckle Senior Member Joined: 21/01/2012 Location: AustraliaPosts: 189 |
My thoughts exactly. I have added the Cocktail Sort to David's test code and it will be in the next update of the library. Cheers, Hugh |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
Hi Hugh, I like that! Thanks! 
But maybe David wishes to change his code and make the variable declaration local? This is not a criticism, just a hint to make the code easier to implement. Regards Michael causality ≠ correlation ≠ coincidence |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Working on it, Michael.
I'm going to code up a Quicksort so it can be tested on 4.6. I don't have a micromite to do the testing on (yet) but others will be able to test it. Best, David |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1671 |
I am glad to hear that!
Regards Michael causality ≠ correlation ≠ coincidence |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Ok, a little feedback... I found a quicksort code that'll work in 4.5... but, all quicksorts are recursive and I think quickly hit the nested GOSUB limit. I can run it in the DOS version for 10 array elements but beyond that, it just stops. Also, here are my sort routines and test code, broken out into two files (test code in .bas and sort routines in .lib). I added LOCAL declarations to try to minimize conflicts. The sort routines still expect predefined array names. 2015-01-17_152345_sorts.zip |
||||
MicroBlocks Guru Joined: 12/05/2012 Location: ThailandPosts: 2209 |
Not ALL quicksorts are reclusive.:) This comes from a sort module I had in my C collection. It is not mine but it worked very well. It does not have the overhead of a stack and function calls, so it is pretty quick. Should be possible to convert it into a basic version. [code] // * Example calls: // quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4 // quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7 void quickSort(int *arr, int elements) { #define MAX_LEVELS 300 int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ; beg[0]=0; end[0]=elements; while (i>=0) { L=beg; R=end-1; if (L<R) { piv=arr  ;
while (L<R) { while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R]; while (arr <=piv && L<R) L++; if (L<R) arr[R--]=arr; }
arr =piv; beg[i+1]=L+1; end[i+1]=end; end[i++]=L;
if (end-beg>end[i-1]-beg[i-1]) { swap=beg; beg=beg[i-1]; beg[i-1]=swap; swap=end; end=end[i-1]; end[i-1]=swap; }} else { i--; }}} [/code] Microblocks. Build with logic. |
||||
| factus10 Regular Member Joined: 30/12/2014 Location: United StatesPosts: 45 |
Thanks, I'll see what I can do. On first glance, I'm not sure it's a quicksort, even though it's named that. For comparison, here's a quicksort, implemented in c: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C |
||||
| Page 1 of 2 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
