![]() |
Forum Index : Microcontroller and PC projects : Need Some Sort Ideas
Page 1 of 2 ![]() ![]() |
|||||
Author | Message | ||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
I've been playing around with storing data on a SPI FRAM chip with great success. Now I need a method to sort all the data to be stored on the FRAM module. The data will not all fit in memory, about 120K, so it needs to be sorted on the FRAM module. I could bubble sort the data (and have) however bubble sorting is a fairly slow method. So, I'm looking for better/faster method to sort up to 2000 records . Basically the data needs to be sorted lowest to highest based on the first 15 columns. Below is a sample of the data: 6154866014 TENNESSEE 201605230834B
5858582103 NEW YORK 201605231337B 6316023230 Shelter Isla NY 201605231900B 2107145488 San Antonio TX 201605271044B 2153025183 Levittown PA 201605311432B 7163280326 Buffalo NY 201606021243B 8609559147 Hartford CT 201606041038B 2025550114 DIST OF COLUMBI 201606081228B 9147023532 NEW YORK 201606091614B 2062370127 Seattle WA 201606101442B Since the FRAM chip I'm using has a 100 Trillion cycles lifespan, I'm not too worried about it wearing out. Thanks, --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
kiiid Guru ![]() Joined: 11/05/2013 Location: United KingdomPosts: 671 |
Alone bubble. Pretty much similar to the bubble sort, with the only difference that after a swap you don't restart from the beginning, but just return to the previous pair of elements. In terms of speed is still not the fastest out there, but definitely not the slowest as well, rather on the faster side. I can dig up my old code in Pascal and will post it tomorrow if that would be of any help. http://rittle.org -------------- |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
In the past I've run the bubble sorts from both ends meeting in the middle, pushing smaller values to one end and larger values to the other in the same pass. I really don't think it's any faster than a regular bubble sort, but it sounds cool. I haven't touched Pascal code since I was in tech school (about 37 years ago), but I'm willing to take a look. Thanks, --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
MicroBlocks![]() Guru ![]() Joined: 12/05/2012 Location: ThailandPosts: 2209 |
Use a merge sort. You can then divide then data into 'blocks', and sort those individually. You size the blocks so that they use the most of the memory to increase speed. Sorting of a block can be done using the bubble sort, as everything is in memory it will be fast enough. You then merge the blocks by comparing each first record from the blocks and write that one into the final 'file'. Point to the next record and do the comparison again, repeat until sorted. Microblocks. Build with logic. |
||||
kiiid Guru ![]() Joined: 11/05/2013 Location: United KingdomPosts: 671 |
Found them, even the explosion one. Good old archives from 1992 ![]() The first one is the alone bubble, the second one is the explosion. procedure sortab; var f : boolean; t,d,x : word; begin f:=false; for x:=1 to max-1 do if a[x]>a[x+1] then begin if f=false then d:=x; f:=true; t:=a[x]; a[x]:=a[x+1]; a[x+1]:=t; if x>1 then dec (x,2) else x:=0; end else if f=true then begin x:=d; f:=false; end; end; procedure sortnew; var l,r,t,s : word; begin l:=1; r:=max; while l+1<r-1 Do begin for t:=l+1 to r do If a ![]() begin s:=a ![]() a ![]() a[t]:=s; end; inc (l); for t:=r-1 downto l do if a[r]<a[t] then begin s:=a[r]; a[r]:=a[t]; a[t]:=s; end; dec (r); end; end; http://rittle.org -------------- |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
There will be little to no memory available for sorting in the Mite itself, so I need to treat this as a "on disk" type of sort. I'm thinking the Modified Bubble Sort may work out since majority of the list is already sorted with the exception of a couple of added records added to the end. Now all I have to do is write a bubble sort routine... ![]() ![]() --Curt I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
kiiid Guru ![]() Joined: 11/05/2013 Location: United KingdomPosts: 671 |
Just quickly typed the alone bubble sort in Basic for you, along with some test code. Here it is: const NUM=100 dim integer a(NUM) dim t,r,x randomize timer for t=1 to NUM a(t)=int(1000*RND()) print a(t);", "; next print:print ' ================================== for r=2 to NUM t=r do while t>1 and a(t-1)>a(t) x=a(t-1) a(t-1)=a(t) a(t)=x t=t-1 loop next ' ================================== for t=1 to NUM print a(t);", "; next print:print Note that the actual sorting is in the part which is separated from the others, the rest is just for the test. http://rittle.org -------------- |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
This is the way I was taught to bubble sort... NUM=100
dim a(NUM) randomize timer for t=1 to NUM a(t)=int(1000*RND()) print a(t);", "; next print:print ' =======Actual Sort Routine======= For i = 1 to NUM - 1 For j = i + 1 TO NUM IF a(i) > a(j) Then t = a(i) a(i) = a(j) a(j) = t EndIf Next j Next i ' ================================== for t=1 to NUM print a(t);", "; next print:print It is not ver efficient, however it is very easy to write and understand. --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
kiiid Guru ![]() Joined: 11/05/2013 Location: United KingdomPosts: 671 |
Well, you can see the difference with naked eye... ![]() The AB sort is much faster without any extra complexity http://rittle.org -------------- |
||||
matherp Guru ![]() Joined: 11/12/2012 Location: United KingdomPosts: 10215 |
Best place I've found for algorithms like sort is rosettacode Every variant of sort you could hope for |
||||
factus10 Regular Member ![]() Joined: 30/12/2014 Location: United StatesPosts: 45 |
I did some work on sorts a couple years ago. The data and sorts are over here. And hey, shout out from Buffalo, one of your data points :) |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
The Bogosort looks like a great sort and I hear it's endorsed by Dirk Gently! ![]() ![]() --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
palcal![]() Guru ![]() Joined: 12/10/2011 Location: AustraliaPosts: 1982 |
This is a way of sorting that I devised about 35 years ago. I don't know if it is a known way of sorting or not. I timed it against "AloneBubble" which took 894 msec this sort took 146 msec. I called it "ArraySort". If two numbers are the same it will only print one of them. Also it may be difficult to load the array with your values. Const NUM=100
Dim integer a(NUM+1) Dim integer x(1010) Dim t Randomize Timer For t=1 To NUM a(t)=Int(1000*Rnd()) x(a(t))=a(t) 'variable x(num) is given the value num Print a(t), Next t Print:Print ' ================================== Do y=y+1 If x(y) > 0 Then Print x(y), Loop Until y=1000 ' ================================== Paul. "It is better to be ignorant and ask a stupid question than to be plain Stupid and not ask at all" |
||||
kiiid Guru ![]() Joined: 11/05/2013 Location: United KingdomPosts: 671 |
I am sorry Paul, but I am failing to understand how would this work. http://rittle.org -------------- |
||||
palcal![]() Guru ![]() Joined: 12/10/2011 Location: AustraliaPosts: 1982 |
Kiiid wrote The part you have printed is only the print out not the sort. Maybe you can't really call it a sort but it is done in the line I commented, x(a(t))=a(t)
I doubt it would work for Justplayin but it works just to do simple numeric sorts. Run my code and see the result. Paul. "It is better to be ignorant and ask a stupid question than to be plain Stupid and not ask at all" |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
Thanks Paul, Unfortunately the sort routine I use will need to work with then data being stored on the FRAM module. With 2000+ records being stored on the FRAM, there will not be enough memory to load it. This limitation will probably prevent me from using some the more efficient sort routines. I think I can greatly reduce the number of records being sorted by skipping those records which do not need to be moved. Such as in this case with the initial data being (1, 3, 4, 6, 9, 12, 14) and I want to add (8, 11, 7). If I pre-scan the new records to be added, I can determine anything less than 7 does not need to be sorted. This would leave ( 9, 12, 14, 8, 11, 7) reducing the amount of data by 40%, which is a huge savings. I've picked a couple of algorithms from Rosetta Code which I need to experiment with to see if any of them are suitable. --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
MicroBlocks![]() Guru ![]() Joined: 12/05/2012 Location: ThailandPosts: 2209 |
You maybe can still load everything in two small arrays in memory if you just take the first letter of the records. First array holds the letter, the second the index. You then sort that in memory. Using the array that holds the index you read/write the records directly from/to FRAM. The next round of sorting would be to take the second letter of the records that have the same first letter and sort that. Then take the third letter of the records that have the same first two letters. Continue until sorted (no more swaps). Microblocks. Build with logic. |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
@ MicroBlocks: Hmmm... Your idea interests me. The problem is, I can't spare the memory (2000 records + 2000 indexes = minimum 12K of RAM probably more like 16K. I will file this idea away for the future though. If the on FRAM sorting is too slow, I may opt for a second Micromite dedicated to managing the FRAM and its data. In which case I would have a lots of RAM (in relative terms) available to work the sorting. Thanks for the idea(s)! --Curtis I am not a Mad Scientist... It makes me happy inventing new ways to take over the world!! |
||||
Justplayin![]() Guru ![]() Joined: 31/01/2014 Location: United StatesPosts: 327 |
Received my 1Mbit (128Kbyte) FRAM chips today and upgraded the Adafruit 64bit (8Kbyte) breakout board. Updated my software to handle the expanded address range then verified write and read operations. Tomorrow I can mock up 2000 records and start testing sort routines. @Grogster – That Chip Qwik stuff is FANTASTIC! I had the 8KB FRAM chip cleanly off in seconds and the post removal cleanup was quick and easy too. Total time to replace the chip was easily under 2 minutes. Thanks for bringing this product to my attention. ![]() --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 |
Curtis, You can use any of these sorts but you need to think of your FRAM as an array. Back in the bad old days, mainframe computers were even less powerful (cpu, amount of ram, etc) than the MM. But they also had a need to sort data. I find it hard to imagine they did it on tape (it would be possible but astoundingly slow)... but they would do it on drum memory (hard drives). In each of the sort examples, there's an dimensioned array to hold data. If you can think of your FRAM as that array, you can adjust these sorts to work with your data. The key issue is random access to your data. How are you storing the data to the FRAM? More important, how are you able to access it? It's been a long time since I've programmed any disk access, but I do recall that most BASICs had the ability to read/write a serial file and a random-access file (of some sort). If MM allows random access to data files (assuming yours is handled that way), you can use these sorts. David |
||||
Page 1 of 2 ![]() ![]() |
![]() |
![]() |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |