| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Indirect Sorting Algorithm
Hi there...
I've written an Indirect Sorting Algorithm!
Whhhooooohhhooo... ;-)
But yeah... It's too slow. :-(
In the code below I can find some little things (few cycles) to speed it up, but this would not do the trick for me.
What does the code do?
It has an 16 bit data array (the elements in the array are 16 bits) and it has an index array. The index array contains indexes to the data array.
First the index array is initialized so that the first index points to the first element in the data array, the second index points to the second element in the data array, and so on...
Then the sorting starts...
It gets the first index and gets the msb of the element the index points to, then compares it to the msb of the element the second index points to. IF the second element is lower then the first, it swaps the indexes, so that the first index isplaced at the second pos in the index table and the second index is placed at the first pos of the index table...
This is the same for the lsb, and the same for all indexes (and elements) of the array.
Normally it goes about 16 times through the code to fully sort a 16 bits array of 16 elements (32 bytes).
Who can help me to speed up this code?
I want it to be twice as fast :-)
And here's the code:
;----------------------------------------------------------
; IndirectSort Routine
;----------------------------------------------------------
;
; Sorts the index table from Low to High
;
; (change the "bcc" commands to "bcs"
; to sort from High to Low)
;
; USES:
; IndexTable An array of indexes. Indexes for the DataArray
; DataTable An array with 16 bit data. The index table has indexes to this array
; ArrayLength A variable filled with the number of elements (not bytes) in the data array.
; DoMoreSort A flag which is set to "true" if more sorting is needed
;
;init index table
ldx #$00
lda #$00
clc
IS_nextIndexInit
sta IS_IndexTable,x
adc #$02
inx
cpx #IS_ArrayLength
bne IS_nextIndexInit
IS_startOfSortPass
;init table index
ldy #$00
;init DoMoreSort flag
lda #false
sta IS_DoMoreSort
IS_checkSwapOnMSB
;get y-pos (msb)
ldx IS_IndexTable,y ;index to y-pos-table
lda IS_DataTable,x ;load y pos (msb)
;compare element with next element (msb)
ldx IS_IndexTable + 1,y ;index to y-pos-table
cmp IS_DataTable,x ;compare y pos (msb)
;check which is higher
beq IS_checkSwapOnLSB
bcc IS_nextIndex ;carry is clear when the second is higher then the first
;swap indexes in index table
lda IS_IndexTable,y
sta IS_IndexTable + 1,y
stx IS_IndexTable,y
;set DoMoreSort flag
lda #true
sta IS_DoMoreSort
;jump to next index
jmp IS_nextIndex
IS_checkSwapOnLSB
;get y-pos (lsb)
ldx IS_IndexTable,y ;index to y-pos-table
lda IS_DataTable + 1,x ;load y pos (lsb)
;compare element with next element (lsb)
ldx IS_IndexTable + 1,y ;index to y-pos-table
cmp IS_DataTable + 1,x ;compare y pos (lsb)
;check which is higher
beq IS_nextIndex
bcc IS_nextIndex ;carry is clear when the second is higher then the first
;swap indexes in index table
lda IS_IndexTable,y
sta IS_IndexTable + 1,y
stx IS_IndexTable,y
;set DoMoreSort flag
lda #true
sta IS_DoMoreSort
IS_nextIndex
iny
cpy #IS_ArrayLength - 1
bne IS_checkSwapOnMSB
;check if sort is ready
lda IS_DoMoreSort
cmp #true
beq IS_startOfSortPass
;done
rts
|
|
| |
WVL
Registered: Mar 2002
Posts: 902 |
This is called 'bubblesort'.
it works pretty fast if the elements are in somewhat correct order to start with, but is completely shit when you have to sort random datasets.
I'd say try a 'binning' algorithm.
in other words :
put elements with certain values (say MSB $00-$10) in one dataset, elements with MSB $10-$20 in another, etc
then do bubblesort (or something else) within the binned datasets. And when done, make one big dataset again.
Anyway, it all depends a lot on the amount of data you want to sort :) Most fast sorting algorithms need more time to set up.
Some more suggestions :
- if you have to sort each frame, like for a sprite multiplexer, google for 'Ocean sort'. It's basically bubblesort, but depends on the sort of the frame before! (useful for multiplexers, since sprites don't move that much between frames, so the sort will almost be the same!)
-google for quicksort if your dataset is really random. |
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Hmm, yeah... I prolly could lower the number of itterations through the code by pre-sorting on only msb.
i.o.w.: Put all the msb = 0 at the top of the data array, and put all the msb = 1 at the bottom of the data array.
but does this seepd up the whole process that much? Doesn't the time for pre-sorting almost equals the time won by pre-sorting?
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Even better...
I could prolly delete the "Init Index Table" code from the routine, so that the sorting is based on the previous sorting results... (thanx WVL :-)
|
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
@WVL
Googling for "Ocean Sort" revealed anything
but a sorting algorithm, even if you try different
combinations together with several other kaywords.
For what did you google???
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
:-)
I found it though...
Google for: "+ocean +sorting +algorithm +c64"
First result is the one you'll be looking for!
|
| |
TNT
Account closed
Registered: Oct 2004
Posts: 189 |
I wrote Shellsort for the MMC64 browser, it can be found at http://www.sci.fi/~tenu/c64/mmc64/shellsort.asm
It doesn't use as much stack as recursive quicksort (although qsort can be improved by sorting larger chunk iteratively and using recursive call only for smaller chunk, in normal cases that helps a lot).
Max. 1500 entries, 8 bytes each:
e_num ds.w 1 ; 00 ordinal in directory, b15 used for dir flag
e_name ds.w 1 ; 02 ptr
e_start ds.w 1 ; 04 cluster
e_size ds.w 1 ; 06 #pages, 0 if dir
Replace Compare-function with your own.
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
@TNT:
Thanx, but ShellSort is not realy applicable for my routine and takes relatively too much cc. Now that I've removed the "re-init index table" part from my routine, and each sort is based on the results of the previouse sort... my routine became at least eight times faster then it was before!!!
|
| |
ready.
Registered: Feb 2003
Posts: 441 |
As far as I tried some time ago, comparing quick sort and bubble sort, the first one is very good with large sets, the second one is better for small sets of variables. Since the problem consists of 16 elements, I'd say bubble sort should be used. |
| |
WVL
Registered: Mar 2002
Posts: 902 |
Quote: @TNT:
Thanx, but ShellSort is not realy applicable for my routine and takes relatively too much cc. Now that I've removed the "re-init index table" part from my routine, and each sort is based on the results of the previouse sort... my routine became at least eight times faster then it was before!!!
\o/
_/-\0_ |
| |
Graham
Account closed
Registered: Dec 2002
Posts: 990 |
Bubblesort is quite good if you have only very few elements (less than 10). After that other sorting algos take over. The "best" is Quicksort which ends with a subdivision size of ~10 elements and after that Insertion sort. Insertion sort needs to move elements within a set and because of this normally has a similar big-O time like Bubblesort, but if you know that it moves the elements max. 10 steps, then it has linear sorting time. And why do you use that instead of full Quicksort? Because Quicksort is very fast in the beginning, but the last elements need a lot more stack action, so the worst part of Quicksort is exchanged for the best part of Insertion sort :) |
| |
Monte Carlos
Registered: Jun 2004
Posts: 359 |
@mrt:thanks for the google tip
@others:
This is a link to several online chapter of "numerical recipes in c":
http://www.library.cornell.edu/nr/bookcpdf.html
look in the chapter 8 with sorting algorithms for different approaches.
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
@Monte Carlos:
Great link! Interesting stuff there! |
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
I've found a way to speed it up even more!
What the main problem was, that it has to look at four bytes to sort two elements (word size). It first looks at the msb of one element and the msb of the next element and after that, it looks at the lsb of one element and the lsb of the next element.
Now what i've done is the following:
1. Create a list of all y-pos with one byte instead of one word per element. One element is formed like this:
lda msb
lsr
lda lsb
ror
sta smallYPos
So, the least-significant-bit is dropped and the most-significant-bit is rolled in.
2. Sorting the one-byte y-pos list with the normal sorting algo (bubble sort) as seen above only omitting the msb sort steps.
Now, this is enough accuracy for my routine, but if you still want to sort the least-significant-bit, you'll need one more step.
3. Do one single sorting pass through the two-byte y-pos table with the normal sorting routine. This only needs one pass, because elements can only go up or down one single place in the table.
Using only the step 1 and 2, the sorting needs only half of the CCs it needed before.
First I dropped the init-table routine (see above), which resulted the sorting to go 8 times as fast.
Now I use one byte instead of one word, which results the sorting routine to go twice as fast.
So in total, the algo needs only a 16th of the origonal CCs now!!!
whoooppyyy!!
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
I'll release the complete code here after our new demo is finished and released. :-) |
