6502.org • View topic

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Sorting?

Page 1 of 1

[ 3 posts ]

Previous topic | Next topic

Author

Message

drogon

Post subject: Sorting?

Posted: Wed Nov 15, 2023 1:46 pm

Joined: Wed Feb 14, 2018 2:33 pm
Posts: 1412
Location: Scotland

The recently excavated thread on Comb Sort http://forum.6502.org/viewtopic.php?f=2&t=1810 gave me a nice diversion before breakfast this morning and the introduction made me ponder enough to think about other ways to do it...

Now, I have in the past done a lot of work in systems with sorts and they are incredibly useful, but I'm by no means an expert and have my favourites, but given the constraints in the original article I was somewhat surprised at the algorithm chosen - of-course it's a demonstration of comb sort, but there is another little favourite of mine when you have those sort of constraints - a small array with a well-defined range of elements - and it's a form of radix or bucket sort, so looking for more little examples and tests for my TinyBasic, I knocked one up in it:

The idea of the bucket sort is that you don't do any compares or swaps - you practically throw away the input data and re-create it by counting each item into a list of buckets, then "re-play" the bucket list back into the output data. It's used when you have well defined inputs (in this case numbers from 0-255) and a limited number on numbers (here, an array 256 elements in size). When data sizes increase it starts to get beyond the capabilities of 8-bit systems very quickly, but can still be used in parts. A common use is in 3D rendering when you want to sort objects by distance so you can draw the furthest away objects first which would them be overdrawn (in part or whole) by closer objects when rendering the scene to a 2D surface - as long as you can sort and draw fast enough you get all the hidden surface hiding for free... In our 6502 world if you have a data set such as described here then you could code this sort and the times will be measurable in microseconds...

So One pass, No compares, No swaps.

Ok, you need a 2nd pass to re-create the actual data and you need double the storage but if you want speed that's the trade-off...

So after I'd satisfied myself this morning I had another look and decided to add bad old Bubble sort and my usual go-to sort which is Shell sort. I was surprised that Comb sort as on-par with Shell sort given it's relative simplicity but not surprised by how slow bubble sort was...

Sort for an array of 256 elements of random numbers: (The same input on all tests)

Bucket sort: 1.07 seconds
Comb sort: 7.34 seconds
Shell sort: 7.67 seconds
Bubble sort: 57.5 seconds

Here is the code for anyone who's interested:

(A few notes: This is my GIBL TinyBasic on a 16Mhz 6502. The ! and ? operators are like peek and poke - ! is for 16-bit words and ? is for 8-bit bytes. !160 = 0 stores 0 in memory locations 160 and 161 and these are the bottom 2 bytes of the 100Hz ticker that's maintained by the underlying OS. TOP is the start of free memory available for strings and arrays).

Code:

NEW

REM Sorts
REM Input is an array of 256 elements of 0-255

100 X = TOP     : REM Input/Output
110 Y = X + 256 : REM Bucket counts

REM Initialise counts and Generate random input

REM Get data

120 GOSUB 800

REM Print Input

129 PR "Original data:"
130 GOSUB 900

REM Bucket Sort

150 GOSUB 600 : PR "Bucket Time: ", T : GOSUB 900

REM Comb

240 GOSUB 800
250 GOSUB 700 : PR "Comb Time: ", T : GOSUB 900

REM Bubble

260 GOSUB 800
270 GOSUB 500 : PR "Bubble Time: ", T : GOSUB 900

REM Shell

280 GOSUB 800
290 GOSUB 400 : PR "Shell Time: ", T : GOSUB 900

299 END

400 !160 = 0 : REM Zero the clock
405 M = 1 : E = 255
410 DO : M = M * 3 + 1 : UNTIL M > E
420 DO
430   M = M / 3
435   FOR I = M TO E
440     V = ?(X+I) : J = I
450     K = J - M
455     IF (K < 0) OR (?(X+K) < V) GOTO 475
460       ?(X+J) = ?(X+K)
465       J = K
470       GOTO 450
475     ?(X+J) = V
477   NEXT I
485 UNTIL M = 1
490 T = !160 : REM Read the clock
499 RETURN

    
REM Classic Bubble Sort
REM ============================================================

500 !160 = 0 : REM Zero the clock
510 FOR I = 0 TO 255
515   FOR J = I TO 255
520     IF ?(X+I) > ?(X+J) T = ?(X+I) : ?(X+I) = ?(X+J) : ?(X+J) = T
530   NEXT J
540 NEXT I
550 T = !160 : REM Read clock
560 RETURN

REM Bucket sort
REM ============================================================

600 !160 = 0 : REM Zero the clock
610 FOR I = 0 TO 255
620   Z = ?(X+I) : Q = Y + Z : REM Index
630   ?Q = ?Q + 1            : REM Count
640 NEXT I

REM Re-Create sorted data from bucket counts

650 J = 0 : FOR I = 0 TO 255
660   C = ?(Y+I) : REM Count in this bucket
670   IF C <> 0 DO : ?(X+J) = I : J = J + 1 : C = C - 1 : UNTIL C = 0
680 NEXT I
690 T = !160 : REM Read clock
699 RETURN

REM Comb/Combination Sort
REM ============================================================

700 !160 = 0 : REM Zero the clock
705 S = 256 : G = 256 : REM Initial values
710 DO
715   G = G * 10 / 13
720   IF G < 1 G = 1
725   W = 0
730   FOR I = 0 TO 255 - G
740     J = I + G
750     IF ?(X+I) > ?(X+J) T = ?(X+I) : ?(X+I) = ?(X+J) : ?(X+J) = T : W = W + 1
760   NEXT I
770 UNTIL (G = 1) AND (W = 0)
780 T = !160 : REM Read clock
799 RETURN

REM Generate Random input (and zero the bucket counters)
REM ============================================================

800 RND = 1234 : REM Seed, so we get the same 'random' numbers
810 FOR I = 0 TO 255
820   ?(X+I) = RND % 256 : ?(Y+I) = 0
830 NEXT I
840 RETURN

REM Print the input array
REM ============================================================

900 @ = 3 : Q = 0
910 FOR I = 0 TO 255
920   PR ?(X+I);
930    Q = Q + 1 : IF Q = 16 Q = 0 : PR ""
940 NEXT I
950 PR ""
960 RETURN

And the outputs to verify:

Code:

Original data:
  81  95 205  19  68 220 193  23  88  65 234  42 139 116 182 222
 192  74 156 192  81  79 144 197 206  83 180  57 153   7  72 108
 180 228 105 255  32 112 101 106 179  28  70 199 231  25  26   1
  41 183  59 236  61  35  52 249  33 142  19 149 245 235  49 119
 159   0 138 219  12  20   6  79 144 120 189 227 195  63  99 229
  14 146 199   8  26   6  75 156   6 171 239 241 209 113 149  27
 252  45  49  38 247  41 186  35 139 213  25 255  61 163 199 200
  18 127  96 181 230 122 239  49  26  70  72 234  43 149 121 190
 167 200  93 130 211  77  94 134 168 176 116 216  25 135  40  44
  53 218  12  81 194 222   0  85  61 253  38 134   8 185 218 195
  68 149 254 110 191 225 245 219  65 143 211 180 118 107 140 145
 218   7 171 124 174 178 164 142 208  25 253  34 100  93 190 231
 111 240  26  75 155 133 171 253 102 234 207  17  82 207  16 116
 253  35 116 152 138 168 250  99 235  52  30  95  64 225 101 138
  12  93 129 151 133 219  15 144  25  71 104 109 206  51 183  88
 130 206 208  66 148 204  81  71 136 209 186 123 220   4 137  47

Bucket Time:  107
   0   0   1   4   6   6   6   7   7   8   8  12  12  12  14  15
  16  17  18  19  19  20  23  25  25  25  25  25  26  26  26  26
  27  28  30  32  33  34  35  35  35  38  38  40  41  41  42  43
  44  45  47  49  49  49  51  52  52  53  57  59  61  61  61  63
  64  65  65  66  68  68  70  70  71  71  72  72  74  75  75  77
  79  79  81  81  81  81  82  83  85  88  88  93  93  93  94  95
  95  96  99  99 100 101 101 102 104 105 106 107 108 109 110 111
 112 113 116 116 116 116 118 119 120 121 122 123 124 127 129 130
 130 133 133 134 134 135 136 137 138 138 138 139 139 140 142 142
 143 144 144 144 145 146 148 149 149 149 149 151 152 153 155 156
 156 159 163 164 167 168 168 171 171 171 174 176 178 179 180 180
 180 181 182 183 183 185 186 186 189 190 190 191 192 192 193 194
 195 195 197 199 199 199 200 200 204 205 206 206 206 207 207 208
 208 209 209 211 211 213 216 218 218 218 219 219 219 220 220 222
 222 225 225 227 228 229 230 231 231 234 234 234 235 235 236 239
 239 240 241 245 245 247 249 250 252 253 253 253 253 254 255 255

Comb Time:  734
   0   0   1   4   6   6   6   7   7   8   8  12  12  12  14  15
  16  17  18  19  19  20  23  25  25  25  25  25  26  26  26  26
  27  28  30  32  33  34  35  35  35  38  38  40  41  41  42  43
  44  45  47  49  49  49  51  52  52  53  57  59  61  61  61  63
  64  65  65  66  68  68  70  70  71  71  72  72  74  75  75  77
  79  79  81  81  81  81  82  83  85  88  88  93  93  93  94  95
  95  96  99  99 100 101 101 102 104 105 106 107 108 109 110 111
 112 113 116 116 116 116 118 119 120 121 122 123 124 127 129 130
 130 133 133 134 134 135 136 137 138 138 138 139 139 140 142 142
 143 144 144 144 145 146 148 149 149 149 149 151 152 153 155 156
 156 159 163 164 167 168 168 171 171 171 174 176 178 179 180 180
 180 181 182 183 183 185 186 186 189 190 190 191 192 192 193 194
 195 195 197 199 199 199 200 200 204 205 206 206 206 207 207 208
 208 209 209 211 211 213 216 218 218 218 219 219 219 220 220 222
 222 225 225 227 228 229 230 231 231 234 234 234 235 235 236 239
 239 240 241 245 245 247 249 250 252 253 253 253 253 254 255 255

Bubble Time: 5750
   0   0   1   4   6   6   6   7   7   8   8  12  12  12  14  15
  16  17  18  19  19  20  23  25  25  25  25  25  26  26  26  26
  27  28  30  32  33  34  35  35  35  38  38  40  41  41  42  43
  44  45  47  49  49  49  51  52  52  53  57  59  61  61  61  63
  64  65  65  66  68  68  70  70  71  71  72  72  74  75  75  77
  79  79  81  81  81  81  82  83  85  88  88  93  93  93  94  95
  95  96  99  99 100 101 101 102 104 105 106 107 108 109 110 111
 112 113 116 116 116 116 118 119 120 121 122 123 124 127 129 130
 130 133 133 134 134 135 136 137 138 138 138 139 139 140 142 142
 143 144 144 144 145 146 148 149 149 149 149 151 152 153 155 156
 156 159 163 164 167 168 168 171 171 171 174 176 178 179 180 180
 180 181 182 183 183 185 186 186 189 190 190 191 192 192 193 194
 195 195 197 199 199 199 200 200 204 205 206 206 206 207 207 208
 208 209 209 211 211 213 216 218 218 218 219 219 219 220 220 222
 222 225 225 227 228 229 230 231 231 234 234 234 235 235 236 239
 239 240 241 245 245 247 249 250 252 253 253 253 253 254 255 255

Shell Time:  767
   0   0   1   4   6   6   6   7   7   8   8  12  12  12  14  15
  16  17  18  19  19  20  23  25  25  25  25  25  26  26  26  26
  27  28  30  32  33  34  35  35  35  38  38  40  41  41  42  43
  44  45  47  49  49  49  51  52  52  53  57  59  61  61  61  63
  64  65  65  66  68  68  70  70  71  71  72  72  74  75  75  77
  79  79  81  81  81  81  82  83  85  88  88  93  93  93  94  95
  95  96  99  99 100 101 101 102 104 105 106 107 108 109 110 111
 112 113 116 116 116 116 118 119 120 121 122 123 124 127 129 130
 130 133 133 134 134 135 136 137 138 138 138 139 139 140 142 142
 143 144 144 144 145 146 148 149 149 149 149 151 152 153 155 156
 156 159 163 164 167 168 168 171 171 171 174 176 178 179 180 180
 180 181 182 183 183 185 186 186 189 190 190 191 192 192 193 194
 195 195 197 199 199 199 200 200 204 205 206 206 206 207 207 208
 208 209 209 211 211 213 216 218 218 218 219 219 219 220 220 222
 222 225 225 227 228 229 230 231 231 234 234 234 235 235 236 239
 239 240 241 245 245 247 249 250 252 253 253 253 253 254 255 255

Cheers,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Top

Chromatix

Post subject: Re: Sorting?

Posted: Mon Dec 18, 2023 4:22 pm

Joined: Mon May 21, 2018 8:09 pm
Posts: 1462

It looks like you're using Knuth's sequence for Shellsort. While it's definitely not the worst one out there, I've found a couple of significantly better ones that are also quite easy to generate.

First is a Modified Sedgewick sequence, essentially 4^k + 3*2^(k-1) + 1 but continued beyond k=1:

Code:

405 M = 4 : N = 3 : E = 255
410 DO : M = M * 4 : N = N + N : UNTIL M + N + 1 > E
420 DO
430   M = M / 4 : N = N / 2 : G = M + N + 1
435   FOR I = G TO E
440     V = ?(X+I) : J = I
450     K = J - G
455     IF (K < 0) OR (?(X+K) < V) GOTO 475
460       ?(X+J) = ?(X+K)
465       J = K
470       GOTO 450
475     ?(X+J) = V
477   NEXT I
485 UNTIL G = 1

In a language that supports bit-shifts, this is very easy and cheap to implement. In BASIC, it's not quite so nice.

If you've heard of Leonardo numbers, they'll almost certainly be in the context of Smoothsort. They're closely related to the Fibonacci numbers; the recurrence is L(n+1) = L(n) + L(n-1) + 1, which converges to the same Golden Ratio as the Fibonacci sequence. But it turns out that if you square the Leonardo numbers, it produces a remarkably good Shellsort sequence - at least for average-case performance. It is also straightforward to implement, and doesn't require divisions to replace bitshifts:

Code:

405 M = 1 : N = 1 : E = 255
410 DO : G = M + N + 1 : M = N : N = G : UNTIL G > E
420 DO
430   G = N : N = M : M = G - N - 1 : G = N * N
435   FOR I = G TO E
440     V = ?(X+I) : J = I
450     K = J - G
455     IF (K < 0) OR (?(X+K) < V) GOTO 475
460       ?(X+J) = ?(X+K)
465       J = K
470       GOTO 450
475     ?(X+J) = V
477   NEXT I
485 UNTIL G = 1

It would be interesting to see how these versions of Shellsort compare on this small sorting problem. Usually investigations of Shellsort performance start in the thousands and run into the millions at least.

Incidentally, the main reason Comb Sort looks competitive is because it eliminates the innermost loop of Shellsort, and thus avoids one set of control-flow overhead, which is particularly expensive in an interpreted language.

Top

IamRob

Post subject: Re: Sorting?

Posted: Mon Dec 18, 2023 9:55 pm

Joined: Sun Apr 26, 2020 3:08 am
Posts: 357

Here is my entry in the fun-to-play-with category. But it requires 3 times the space that the data holds.

Tree Sort

1 FOR E=2 TO 255
2 G=1
3 IF A(E)<A(G) THEN H=G : G=A(H) : ON G>0 GOTO 3 : A(H)=E : NEXT : END
4 H=G : G=B(H) : ON G>0 GOTO 3 : B(H)=E
6 NEXT : END

10 REM To display the sorted list
12 J=1 : G=1
14 IF A(G) > 0 THEN K(J)=G : L(J)=1 : J=J+1 : G=A(G) : GOTO 14
16 PRINT A(G) : IF B(G)>0 THEN K(J)=G : L(J)=0 : J=J+1 : G=B(G) : GOTO 14
18 J=J-1 : G=K(J) : ON L(J)>0 GOTO 16 : ON J>0 GOTO 18

Also of note, the comb sort starts to do very poorly on strings when there are more than 300 strings.

Also an ML program just takes 30 bytes to do a bubble sort of 255 numbers

0300:A2 00 A0 00 E8 B9 00 10 DD 00 10 90 0B 48 BD 00
0310:10 99 00 10 68 9D 00 10 E8 D0 EA C8 D0 E7 60

Top

Page 1 of 1

[ 3 posts ]

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 10 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum