Home
JAQForum Ver 24.01
Log In or Join  
Active Topics
Local Time 04:52 07 Jul 2025 Privacy Policy
Jump to

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 : Need Some Sort Ideas

     Page 1 of 2    
Author Message
Justplayin

Guru

Joined: 31/01/2014
Location: United States
Posts: 327
Posted: 09:03am 20 Jun 2016
Copy link to clipboard 
Print this post

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,
--CurtisEdited by Justplayin 2016-06-21
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 Kingdom
Posts: 671
Posted: 10:28am 20 Jun 2016
Copy link to clipboard 
Print this post

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 States
Posts: 327
Posted: 10:50am 20 Jun 2016
Copy link to clipboard 
Print this post

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.

  Quote  I can dig up my old code in Pascal and will post it tomorrow if that would be of any help.

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: Thailand
Posts: 2209
Posted: 06:18pm 20 Jun 2016
Copy link to clipboard 
Print this post

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 Kingdom
Posts: 671
Posted: 10:15pm 20 Jun 2016
Copy link to clipboard 
Print this post

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>a[t] then
begin
s:=a;
a:=a[t];
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 States
Posts: 327
Posted: 07:53am 21 Jun 2016
Copy link to clipboard 
Print this post

  MicroBlocks said   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.


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... Turns out the way I learned bubble sorting is not what other people learned. When I tried to add the "no swap" flag variable to my version it terminates the sort prematurely without sorting anything.

--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 Kingdom
Posts: 671
Posted: 09:28am 21 Jun 2016
Copy link to clipboard 
Print this post

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 States
Posts: 327
Posted: 11:31am 21 Jun 2016
Copy link to clipboard 
Print this post

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 Kingdom
Posts: 671
Posted: 07:53pm 21 Jun 2016
Copy link to clipboard 
Print this post

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 Kingdom
Posts: 10215
Posted: 09:06pm 21 Jun 2016
Copy link to clipboard 
Print this post


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 States
Posts: 45
Posted: 07:45am 22 Jun 2016
Copy link to clipboard 
Print this post

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 :)Edited by factus10 2016-06-23
 
Justplayin

Guru

Joined: 31/01/2014
Location: United States
Posts: 327
Posted: 09:37am 22 Jun 2016
Copy link to clipboard 
Print this post

  matherp said  
Best place I've found for algorithms like sort is rosettacode

Every variant of sort you could hope for


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: Australia
Posts: 1982
Posted: 07:20pm 22 Jun 2016
Copy link to clipboard 
Print this post

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 Kingdom
Posts: 671
Posted: 10:17am 23 Jun 2016
Copy link to clipboard 
Print this post

  palcal said  
' ==================================
Do
y=y+1
If x(y) > 0 Then Print x(y),
Loop Until y=1000
' ==================================

Paul.


I am sorry Paul, but I am failing to understand how would this work.

http://rittle.org

--------------
 
palcal

Guru

Joined: 12/10/2011
Location: Australia
Posts: 1982
Posted: 10:45am 23 Jun 2016
Copy link to clipboard 
Print this post

Kiiid wrote
  Quote  
I am sorry Paul, but I am failing to understand how would this work.


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 States
Posts: 327
Posted: 11:12am 23 Jun 2016
Copy link to clipboard 
Print this post

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: Thailand
Posts: 2209
Posted: 07:59pm 23 Jun 2016
Copy link to clipboard 
Print this post

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 States
Posts: 327
Posted: 11:24am 24 Jun 2016
Copy link to clipboard 
Print this post

@ 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 States
Posts: 327
Posted: 06:42pm 24 Jun 2016
Copy link to clipboard 
Print this post

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 States
Posts: 45
Posted: 04:36am 26 Jun 2016
Copy link to clipboard 
Print this post

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    
Print this page
The Back Shed's forum code is written, and hosted, in Australia.
© JAQ Software 2025