Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Indirect Sorting Algorithm
2005-12-14 14:47
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


2005-12-14 15:39
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.
2005-12-14 15:47
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?
2005-12-14 16:05
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 :-)
2005-12-14 18:20
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???


2005-12-14 20:02
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!
2005-12-14 21:28
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.
2005-12-15 07:12
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!!!
2005-12-15 12:21
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.
2005-12-15 12:58
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_
2005-12-15 13:07
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 :)
 
... 4 posts hidden. Click here to view all posts....
 
Previous - 1 | 2 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Alakran_64
Peacemaker/CENSOR/Hi..
Scrap/Genesis Project
t0m3000/hf^boom!^ibx
Perplex/Offence
CreaMD/React
Knut Clausen/SHAPE/F..
Sillicon/Unreal
The Human Co../Maste..
Dr.Science/Atlantis
Malmix/Fatzone
ΛΛdZ
kbs/Pht/Lxt
MCM/ONSLAUGHT
Guests online: 130
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.7)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)
Top Coders
1 Axis  (9.8)
2 Graham  (9.8)
3 Lft  (9.8)
4 Crossbow  (9.8)
5 HCL  (9.8)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.074 sec.