TheBackShed.com

Forum Index : Microcontroller and PC projects : Sorting data

Page 2 of 2

Author

Message

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 01:05am 20 Jan 2015

Copy link to clipboard

Print this post

Thank you!

Quote all quicksorts are recursive and I think quickly hit the nested GOSUB limit.

I think, modern Basics (and Basic programmer) never need GOSUBs! You can replace it anytime with Subroutines and Functions.

Btw. did you see Peters (G8JCF) "Guidelines for Creating Libraries for MMBasic"?
Useful also for Maximites!

Regards
Michael

causality ≠ correlation ≠ coincidence

factus10
Regular Member

Joined: 30/12/2014
Location: United States
Posts: 45

Posted: 05:05am 20 Jan 2015

Copy link to clipboard

Print this post

When I say GOSUB limit, I'm assuming there's a stack associated with subroutine calls. The interpreter has to know where to return at the end of a subroutine.

Usually, the interpreter will push return info on to a stack and pop it back off as the code comes back from the subroutines.

Geoff could say for sure, though.

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 06:13am 20 Jan 2015

Copy link to clipboard

Print this post

Quote When I say GOSUB limit, I'm assuming there's a stack associated with subroutine calls. The interpreter has to know where to return at the end of a subroutine.

That's correct!

From Geoffs MMBasic Manual (Maximite):

Quote Maximum number of nested GOSUBs is 100.

This also applies to Subroutines and Functions! 100 nested calls are the limit (MMBasic 4.5 for Maximites).

Sorry for the misunderstanding!

Regards
Michael

causality ≠ correlation ≠ coincidence

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 06:11am 16 Apr 2015

Copy link to clipboard

Print this post

This is a BUGFIX for Davids (factus10@TBS) Comb Sort.
(I greatly appreciate his his contribution! Thanks again!)

' Provided AS IS without any warranty.
' Use it at your own risk. All information is provided for
' educational purposes only!

sub nCombSort(ArraySize)
'----------------------------------------------------------
' Comb sort
' http://en.wikipedia.org/wiki/Comb_sort
'
' This is a pretty efficient and quick sort.
' This sort expects you to pass the number of elements in the
' array as Arraysize.
' It will sort an array of numeric values called called mArnum.
'----------------------------------------------------------
'
local Gap, Shrink, swapped,i
Gap = ArraySize
Shrink = 1.3

do while Gap>1 or swapped
Gap = int(Gap/Shrink)
if Gap < 1 then
Gap = 1
endif

i = 0
swapped = 0

do while i + Gap <= ArraySize
if mArnum(i) > mArnum(i+Gap) then
SWAP mArnum(i), mArnum(i+Gap)
Swapped = 1
endif
i = i + 1
loop

loop
end sub

sub aCombSort(ArraySize,CaseSensitive)
'----------------------------------------------------------
' Comb sort
' http://en.wikipedia.org/wiki/Comb_sort
'
' This is a pretty efficient and quick sort.
' This sort expects you to pass the number of elements in the
' array as Arraysize.
' It will sort an alphanumeric array called x$.
' If CaseSensitive is TRUE, it'll pay attention to mIxEd case
' values. Otherwise, it will lowercase the values to compare.
'----------------------------------------------------------
'
local Gap, Shrink, swapped,i
Gap = ArraySize
Shrink = 1.3

do while Gap>1 or swapped
Gap = int(Gap/Shrink)
if Gap < 1 then
Gap = 1
endif

i = 0
swapped = 0

do while i + Gap <= ArraySize
if (CaseSensitive) then
if x$(i) > x$(i+Gap) then
STRSWAP x$(i), x$(i+Gap)
Swapped = 1
endif
else
if lcase$(x$(i)) > lcase$(x$(i+Gap)) then
STRSWAP x$(i), x$(i+Gap)
Swapped = 1
endif
endif
i = i + 1
loop
loop
end sub

I also provided some (very) simple test procedures.

2015-04-16_160827_sorts2.zip

Regards
Michael

causality ≠ correlation ≠ coincidence

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 06:03am 10 Aug 2017

Copy link to clipboard

Print this post

Update
This is a optimized version of factus aCombSort for strings.

' Comb Sort
' an optimized (8/2017 by twofingers@TBS) version of aCombSort for strings.
' It sorts the array S$() and needs the number of elements to sort (STop)
' Usage: oCombSort S$(),STop
'
' It takes 330ms (or less) for an array of 100 elements
' System: MM2/48MHz/MMBasic 5.04.05
'
Sub oCombSort(S$(),STop)
Local string M$
Local integer i, h, T=1, F=0, sw
Local float Gap=STop, Shrink=1.3

Do While Gap>1 Or Sw
Gap=Int(Gap/Shrink)
If Gap<1 Then Gap=1
i=1:Sw=F
For h=i+Gap To STop
If S$(i)>S$(h) Then
M$=S$(i):S$(i)=S$(h):S$(h)=M$:Sw=T
EndIf
i=i+1
Next
Loop
End Sub

Demo
2017-08-10_155726_TBS_Comb_Sort_Demo.zip

Michael

causality ≠ correlation ≠ coincidence

paceman
Guru

Joined: 07/10/2011
Location: Australia
Posts: 1329

Posted: 01:10am 11 Aug 2017

Copy link to clipboard

Print this post

It would be interesting to see this added to the 'sort comparison' on CaptainBoing's Fruitoftheshed page here
BTW Michael, did you or anyone else do a cFunction sort e.g. along the lines of MicroBlock's C code post (page 2 of this thread)?

Greg

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 03:01am 11 Aug 2017

Copy link to clipboard

Print this post

Hi Greg,

after hours of research and millions of test data to sort I can say, compared with the other sort routines on the Fruitoftheshed library the procedure above is the fastest (in plain Basic).

AFAIK Peter (matherp) made a good working and well documented CFunction (STRINGSORT, INTEGERSORT, FLOATSORT) which is part of the MMBasic distribution. (Thanks for that!

)

But sometimes it's not enough just to sort one array, you have also to sort the corresponding array (ie name, city, birthday etc.). Then the Basic code is more flexible to modify (just change the swap part). And for MMBasic for DOS, Raspberry and MMX we can't have a CFunction.

causality ≠ correlation ≠ coincidence

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 05:19am 11 Aug 2017

Copy link to clipboard

Print this post

paceman said It would be interesting to see this added to the 'sort comparison' on

here it is. Very close but the comb just about has the edge - there are odd bumps where CR" overtakes again though - worst case orders I am guessing. I will update the articles later - I'll spin out the comparison and working data into a separate article.

I am running a larger test on 1000 items as I can squeeze into RAM for just the Shell, CR2 and Comb to see if there is any convergence or reversals. I may be some time

Timings may be slightly different from the original article because this test MM had it's CLOCKTRIM tweaked, so at least these are fairly precise mS

Times in mS for the below sorts
No. BBL Shell CR2 COMB
---------------------------------------
5 10 9 2 7
6 16 13 8 9
7 17 15 8 10
8 19 14 13 14
9 21 15 11 14
10 23 24 14 14
11 26 27 16 18
12 28 30 19 20
13 29 31 20 20
14 32 36 27 21
15 66 39 26 26
16 72 41 31 28
17 77 44 33 29
18 81 51 35 31
19 86 52 39 38
20 93 50 42 37
21 98 52 44 41
22 101 60 48 43
23 107 64 49 43
24 113 79 51 45
25 136 81 53 55
26 141 83 62 53
27 172 86 65 54
28 182 89 70 60
29 191 93 72 62
30 199 98 72 68
31 207 103 76 72
32 238 109 77 73
33 256 117 78 68
34 269 119 89 76
35 302 123 92 78
36 310 122 92 83
37 319 125 96 85
38 328 134 101 85
39 336 139 103 87
40 399 137 105 91
41 409 139 107 94
42 452 147 117 105
43 460 150 119 105
44 487 150 122 108
45 505 155 122 112
46 516 152 128 109
47 528 159 132 116
48 545 171 136 118
49 603 178 137 123
50 619 173 143 123
51 629 176 144 124
52 640 186 156 127
53 656 192 159 128
54 667 226 162 141
55 682 228 165 146
56 694 228 164 149
57 708 230 167 152
58 723 240 175 172
59 921 242 178 160
60 972 250 189 182
61 998 257 190 172
62 1024 267 190 180
63 1048 265 197 164
64 1071 265 207 169
65 1095 265 203 168
66 1119 273 210 172
67 1142 278 215 204
68 1153 291 222 191
69 1177 299 226 199
70 1199 297 230 203
71 1222 298 236 206
72 1245 297 233 210
73 1258 301 237 207
74 1274 315 249 211
75 1297 318 241 214
76 1322 327 246 218
77 1348 335 253 220
78 1369 334 260 224
79 1396 336 263 229
80 1414 340 257 250
81 1433 345 263 230
82 1453 336 280 250
83 1777 345 280 255
84 1805 354 288 300
85 1820 358 294 239
86 1925 373 296 246
87 1947 376 302 250
88 1972 386 307 293
89 1996 390 312 276
90 2013 389 314 300
91 2050 392 320 288
92 2069 389 318 291
93 2180 386 322 288
94 2199 418 327 293
95 2231 429 334 314
96 2252 442 333 318
97 2270 445 336 299
98 2287 416 339 303
99 2317 417 343 327
100 2344 450 351 330

Edited by CaptainBoing 2017-08-12

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 07:05am 11 Aug 2017

Copy link to clipboard

Print this post

Hi Andrew,

thanks, that's exactly what I found out!

I sorted arrays of 10000 elements and more with MMBasic for DOS. That saves you time.
I have also used pre-sorted data, inverse sorted data etc. without big differences.

Can you please try to verify all of the sorted datas? Hint: CR2sort works better (but not perfekt) if I set b=0.

My code to verify:

spo$=""
errorcounter=0
For i = 1 To xx
' Print i,sp$(i)
If spo$ > sp$(i) Then
Print "COMBSORT Error!",spo$,sp$(i)
errorcounter=errorcounter+1
EndIf
spo$=sp$(i)
Next

causality ≠ correlation ≠ coincidence

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 08:41am 11 Aug 2017

Copy link to clipboard

Print this post

hey Michael - yes I will do a verify on a complete set once the current run is finished. I am doing a thousand and currently at ~650 - it's gonna take a while. once the time trials are done I will do one more at a thousand items and verify each time.

This has been (so far) a very absorbing thread for me

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 09:11am 11 Aug 2017

Copy link to clipboard

Print this post

I hope it's worth it for you!

causality ≠ correlation ≠ coincidence

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 09:16am 11 Aug 2017

Copy link to clipboard

Print this post

it's 'mites... a labour of love

(780)Edited by CaptainBoing 2017-08-12

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 11:47am 11 Aug 2017

Copy link to clipboard

Print this post

OK, All finshed.

the new article and the modified articles are availble here.

Bit tired, so there is probably lots of errors - please feel free to correct as necessary.

An interesting diversion and a surprising results graph. It seems the comb sort starts to become erratic at around 1000 items, so I am running again with just the CR2 & comb sorts at 2200 items, just as an academic exercise.

results in the morning. zzzzzEdited by CaptainBoing 2017-08-12

paceman
Guru

Joined: 07/10/2011
Location: Australia
Posts: 1329

Posted: 08:05pm 11 Aug 2017

Copy link to clipboard

Print this post

Michael & Andrew - Great, thanks for that - talk about ask and ye shall receive!

I checked the MMBasic documentation and sure enough as you say, Peter has put cFunctions in there for floats, integers and strings. Thanks Peter and I'll check before I open my mouth next time.

I take your point too Michael about needing to sort other elements and thus the slower but easily modifiable Basic code being still very relevant - horses for courses again.

Andrew - just checked out your modded 'fruitoftheshed' post - thanks for your time doing that. I think it's good to have it all in one place and the wiki is just the place for it - maybe a comment re Peter's sorting cFunctions being available in the MMBasic documentation would be a good addition to that page too.

It's interesting how the CR2 sort's curve is very 'noiseless' compared to the comb sort and the 'baseline' of the comb curve is sort of even compared to the 'noise' above it. I guess if your code needed to know pretty closely how long a given no of elements would take to sort then CR2 might be the way to go, whereas it seems 'comb' is the quickest overall - albeit marginally.

Greg

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 09:26pm 11 Aug 2017

Copy link to clipboard

Print this post

It has been am enjoyable canter.

The race between the CR2 and Comb with 2000+ elements is still running! (Michael's note about doing it with MMBasic4DOS is a cautionary tale

) but at 1916 elements, the timings are 12014 and 10432 respectively so my fears regarding worst case seem unfounded, but yes I thought it was interesting the way Comb has "senior moments" and spikes above it's baseline curve, even taking longer than CR2. But I think that is over now - I can't imagine a spike taking +2 seconds... but we shall see.

Peter said he has no problem with his public code going up on the Wiki so I will definitely post his CFunctions, especially to stop someone using a pure MMBasic sort out of ignorance of a better solution. Don't want someones application being slowed un-necessarily.
Edited by CaptainBoing 2017-08-13

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 08:28pm 12 Aug 2017

Copy link to clipboard

Print this post

CR2 vs Comb time comparison

Comb is faster overall but I think the the graph demonstrates the interesting phenomenon of "worst case" order. A number of searches suffer from this but it is rarely likely to be a problem in real life, just unlucky if it is.

better resolution is available at the bottom of this article.Edited by CaptainBoing 2017-08-14

twofingers

Guru

Joined: 02/06/2014
Location: Germany
Posts: 1671

Posted: 01:57am 13 Aug 2017

Copy link to clipboard

Print this post

Hi Andrew,

as you know I really appreciate your commitment!

But I have some issues to use the CR2 sort, sorry!

In the range up to ~30 items it fails (for random data strings).
With your predefined data set I get errors for data sets with up to 14 items.
I think, you should know that.

I know that you have invested a lot of work, maybe it is just a small bug or
something system specific (floating point related?).

'
' This code is made to demonstrate that
' CR2 sort fails for smaller amounts of data
' (up to 30 items).
'
' Modified test program by twofingers@TBS
' original by CaptainBoing@TBS 2017
'

Option base 0
Dim xx,yy,t As integer
xx=25
Dim SP$(xx)
For yy = 6 To xx
Print "For";yy;" elements:"
GoTo L1
InitSP yy:Timer=0
BblSort yy
t=Timer:Print "BBLSORT=";t;"mS "
InitSP yy:Timer=0
ShellSort yy
t=Timer:Print "SHELLSORT=";t;"mS"
L1: InitSP yy:Timer=0
For i = 1 To yy
Print i,SP$(i)
Next i
CR2Sort yy
t=Timer:Print "CR2SORT=";t;"mS"
' -------------------------------
' verify
SPo$=""
For i = 1 To yy
Print i,SP$(i)
If SPo$ > SP$(i) Then
errorcounter=errorcounter+1
Print
For h = 1 To elements
Print h,SP$(h)
Next
Print
Print "CR2SORT Error! at pos " i:Print SPo$,SP$(i)
EndIf
SPo$=sp$(i)
' Pause 20
Next
' -------------------------------
Print
Next
end
'-----------------------------------------------------------------
' Cube Root of Two Sort
Sub CR2SORT(SPtop)
Local INTEGER i,x,b
Local FLOAT p,y
Local STRING a$
p=1.2599211: x=2: b=1: y=SPtop\2
While y>2: y=y/p: Wend
While x>1
y=y*p
x=SPtop\y
For i=0 To SPtop-x
If SP$(b+i)>SP$(x+i) Then a$=SP$(b+i):SP$(b+i)=SP$(x+i):SP$(x+i)=a$ 'SWAP SP$(b+i),SP$(x+i)
Next
Wend
End Sub
'-----------------------------------------------------------------
' Shell Sort
Sub ShellSort(SPTop)
Local integer i,j
Local float k
Local string a$
k = Int(SPTop / 2)
While k > 0
For i = 1 To SPTop
j = i
a$ = SP$(i)
While (j >= k+1 And SP$(Abs(j-k)) > a$)
SP$(j) = SP$(j-k)
j = j - k
Wend
SP$(j) = a$
Next
If k = 2 Then
k = 1
Else
k = Int(k * 0.454545) ' 5/11
End If
Wend
End Sub
'-----------------------------------------------------------------
' Bubble Sort
Sub BblSort(SPTop)
' SP$() is the array to be sorted
' SPTop is the number of elements in the array
Local integer Flips,n
Local string a$
Flips = 1
Do
Flips = 0
For n=0 To SPTop-1
' took out SWAP A$(n),A$(n+1) as it added 50% to the time
If SP$(n) > SP$(n+1) Then a$=SP$(n):SP$(n)=SP$(n+1):SP$(n+1)=a$:Flips = 1
Next
Loop While Flips = 1
End Sub
'-----------------------------------------------------------------
' Initialise the data-set
Sub InitSP(x)
Local integer n
Restore
For n=0 To x:Read SP$(n):Print n, SP$(n):Next
Print
End Sub
Data "zak","sheila","fred","archie"
Data "jim","barry","alan","kevin"
Data "charles","steve","stephanie","jon"
Data "sonia","xavier","mark","adi"
Data "darren","paul","toby","jp"
Data "josie","kingsley","vod","oregon"
Data "lou anne","ian","syed","craig"
Data "james", "jules","judith","julie"
Data "fargo","david","hanson","dakota"
Data "picard", "riker", "morn", "quark"
Data "cisco", "morgan","bennett","white"
Data "black","brown","red","orange"
Data "green","blue","grey","violet"
Data "smith","kadiyam","shah","moore"
Data "saxton","murray","mitchell","alaie"
Data "aa","bb","cc","dd"
Data "ee","ff","gg","gg"
Data "[Bzz","hh","ii","jj"
Data "hgjhg","ufyf","serg","iuyyrre"
Data "hiuhiuh","fdresppokm","khgugftrdtrhtfyguguF","gfhf"
Data "pic","micro","microchip","atmel"
Data "intel","zilog","amd","nvidia"
Data "mitsubishi","nissan","volkswagen","bmw"
Data "tesla","audi","toyota","honda"
Data "suzuki","yamaha","yamaha","kawasaki"
Data "mike"

This is a test program for comparisation Comb vs CR2 sort.
Something to play with:
2017-08-13_114417_TBS_Comb_vs_CR2_Sort.zip

I hope, that makes things a little bit clearer ...

Regards
Michael

causality ≠ correlation ≠ coincidence

CaptainBoing

Guru

Joined: 07/09/2016
Location: United Kingdom
Posts: 2171

Posted: 02:06am 13 Aug 2017

Copy link to clipboard

Print this post

Final words on the comparison: here

@twofingers Yes I have seen that in action too but can't really pinpoint the reason. I thought it might be because of the single precision nature of the maths too (the originals were double). However...

As this experiment has proven, there are better methods so beyond the academic exercise, there isn't much point in trying to iron out the problem

please feel free to update the wiki though if you want to. I will edit the article to highlight the sort failure tho' just to stop it being used.
Edited by CaptainBoing 2017-08-14

paceman
Guru

Joined: 07/10/2011
Location: Australia
Posts: 1329

Posted: 03:31am 13 Aug 2017

Copy link to clipboard

Print this post

Very interesting stuff gents and now all together in one place we can all access.

Greg

Page 2 of 2

Print this page

To reply to this topic, you need to log in.