Assember: 16bit bubble sort

Страница 1/5
| 2 | 3 | 4 | 5

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 00:45

Today I needed 16bit sorting routine... Feel free to use, if you need:


	;Input BC = Number of words to sort (Min 2)

	LD BC,(DATAE-DATAS)/2

WBUBBLE:

	DI
	DEC BC
	INC B
	LD IYL,B
	LD IYH,C
	LD (.STORSP),SP
.LOOPO
	LD IXL,1
	LD B,IYH
	LD C,IYL
	LD SP,DATAS    ; Data to be sorted out
	POP HL
.LOOPI
	POP DE
	LD A,D    ; Swap D & H to turn around
	CP H      ;
	JR C,.SWAP
	LD A,E    ; Swap E & L to turn around
	CP L      ;
	JR C,.SWAP
	EX DE,HL
	DJNZ .LOOPI
	JP .CHECK
.SWAP
	PUSH HL
	PUSH DE
	POP DE
	POP HL
	LD IXL,0
	DJNZ .LOOPI
.CHECK:
	DEC C
	JP NZ,.LOOPI
	LD A,IXL
	AND A
	JP Z,.LOOPO
	LD SP,0
.STORSP: EQU $-2
	RET


; Example data:

DATAS:   DW 0,1,2,3,4,5,4,3,2,1,0
DATAE:

Для того, чтобы оставить комментарий, необходимо регистрация или !login

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 02:36

Here is also 8bit version:


        ;Input BC = Number of bytes to sort (Min 2)

        LD BC,DATAE-DATAS

BUBBLE8:
        DEC BC
        LD IYH,B
        LD IYL,C
.LOOPO
        LD IXL,1
        LD B,IYH
        LD C,IYL
        LD DE,DATAS    ; Data to be sorted out
        LD H,D
        LD L,E
        INC HL
.LOOPI
        LD A,(DE)
        CP (HL)
        JR C,.SWAP
        INC DE
        CPI
        JP PE,.LOOPI
        JP .CHECK
.SWAP
        LDI
        LD (DE),A
        LD IXL,0
        JP NZ,.LOOPI
.CHECK:
        LD A,IXL
        AND A
        RET NZ
        JP .LOOPO


; Example data:

DATAS:   DB 0,1,2,3,4,5,4,3,2,1,0
DATAE:

By WORP3

Paladin (828)

Аватар пользователя WORP3

26-07-2011, 09:30

If you want it to be fast it's better to forget about the bobble sort in total, try using the insertion sort.
The insertion sort is also a simple (also not the quickest) method that is a lot faster then the bubble sort.

See: http://en.wikipedia.org/wiki/Insertion_sort

By yzi

Champion (444)

Аватар пользователя yzi

26-07-2011, 09:43

Bubble sort is the slowest possible sorting algorithm that doesn't perform any steps/swaps that would decrease the "sortedness" of the array of elements. I remember this being proven on some basic computer science lecture...

Bogo sort is even slower, but it's based on randomly shuffling the elements until they're in the wanted order, so it performs those harmful swaps that bubble sort doesn't.
http://en.wikipedia.org/wiki/Bogosort

NYYRIKKI's sorting code looks quite small, though.

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 10:28

If you want it to be fast it's better to forget about the bobble sort in total, try using the insertion sort.
The insertion sort is also a simple (also not the quickest) method that is a lot faster then the bubble sort.

See: http://en.wikipedia.org/wiki/Insertion_sort

Well... Remove the outer loop (LOOPO) and you have your insertion sort. (Put value to begin of table, dec DATAS by 2 and inc BC) Ok, the table then grows backwards, but it is fast. 8bit version is easy to turn to grow other way around as well. (Init to end and then use DEC DE, CPD, LDD)

By doing more complex sorts the problem is that Z80 has so little registers that you easily end up wasting the saved time by swapping data in and out from memory. Sure it depends, how much data you have to sort and how much it is messed up. I just needed something little that works, but indeed modifying this to insertion sort is a good idea. Usually I do one iteration of Bubble/insertion sort each time I add a value.

By WORP3

Paladin (828)

Аватар пользователя WORP3

26-07-2011, 11:26

Your absolutely right, it all comes down to the amount of data you have to sort !
If you keep track of the highest inserted value (at the end of the new table), yo can make a simple decision if it is needed to search for a specific value or just add the new value at the end of the table Wink

By enribar

Paragon (1144)

Аватар пользователя enribar

26-07-2011, 14:33

Under certain conditions, counting-sort is the quickest, time complexity O(n) (insertion-sort and bubble-sort are O(n^2) ).
Insertion and bubble are in-place sorting algorithms, while counting requires additional memory space, but it is stable so in theory it provides benefits to sprite sorting (same shape but different sprite identity).

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 14:37

Hmm... I just noticed that there is bug in the 8bit-version. After LDI there should be ofcource JP PE and not JP NZ.

Here is "Insertion sort" version of the 8bit version:

	;Input BC = Number of bytes to sort (Min 2)

	LD BC,DATAE-DATAS

INSERT8:
	EXX
	LD BC,0
.LOOPO
	INC BC
	PUSH BC
	EXX
	CPI
	JP PO,.EXIT
	LD HL,DATAS	; Data to be sorted out
	ADD HL,BC
	PUSH HL
	EXX
	POP HL
	LD D,H
	LD E,L
	DEC DE

.LOOPI
	LD A,(DE)
	CP (HL)
	JR C,.SWAP
	INC DE
	CPI
	JP PE,.LOOPI
	POP BC
	JP .LOOPO

.SWAP
	LDI
	LD (DE),A
	JP PE,.LOOPI
	POP BC
	JP .LOOPO

.EXIT	RET


; Example data:

DATAS:	DB 0,1,2,3,4,5,4,3,2,1,9
DATAE:

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 15:40

Here is "Insertion sort" for 16bit values:

	;Input BC = Number of words to sort (Min 2)

	LD BC,(DATAE-DATAS)/2

INSERT16:

	DI
	LD HL,DATAS	; Data to be sorted out
	LD (.STORSP),SP
	LD IX,0
	DEC BC
	ADD HL,BC
	ADD HL,BC
	EXX
.LOOPO
	INC IX
	LD B,IXH
	LD C,IXL
	EXX
	CPD
	JP PO,.EXIT
	DEC HL
	LD SP,HL
	EXX
	POP HL
.LOOPI
	POP DE
	LD A,D
	CP H
	JR C,.SWAP
	LD A,E
	CP L
	JR C,.SWAP
	CPI
	EX DE,HL
	JP PE,.LOOPI
	JP .LOOPO
.SWAP
	PUSH HL
	PUSH DE
	CPI
	POP DE
	POP HL
	JP PE,.LOOPI
	JP .LOOPO
.EXIT:
	LD SP,0
.STORSP: EQU $-2
	RET


; Example data:

DATAS:	DW 0,1,2,3,4,5,4,3,2,1,0
DATAE:

By Tanni

Hero (556)

Аватар пользователя Tanni

26-07-2011, 18:39

If you want it to be fast it's better to forget about the bobble sort in total, try using the insertion sort.
The insertion sort is also a simple (also not the quickest) method that is a lot faster then the bubble sort.

Depends. For very small arrays, bubble sort is the fastest. That's why it is or could be used for supersort.


Under certain conditions, counting-sort is the quickest, time complexity O(n) (insertion-sort and bubble-sort are O(n^2) ).
Insertion and bubble are in-place sorting algorithms, while counting requires additional memory space, but it is stable so in theory it provides benefits to sprite sorting (same shape but different sprite identity).

Never heard of counting sort, at least not under this name. What do you mean by ''in place''? There's something called topological sorting, which is ''in place''. Bubble sort exchanges elements, so they don't stay in place. For sorting an array of n elements, you at least need O(n log n) steps.

By NYYRIKKI

Enlighted (5889)

Аватар пользователя NYYRIKKI

26-07-2011, 19:46

Yet another error in 8bit version... I did forget to POP BC on exit.

Ok, now here is already pretty well optimized 8bit insertion sort:

(I don't know why I do this to my self... The very first version already did all that I needed but now I'm stuck in optimizing these stupid routines)

	;Input BC = Number of bytes to sort (Min 2)
	LD BC,DATAE-DATAS

INSERT8:
	LD HL,DATAS ; Data to be sorted out
	ADD HL,BC
	EXX
	LD IX,0
	DB #3E
.NextSort:
	LD (DE),A
	EXX
	CPD
	JP PO,.EXIT
	PUSH HL
	EXX
	POP HL
	INC IX
	LD B,IXH
	LD C,IXL
	LD D,H
	LD E,L
	DEC DE
	LD A,(DE)
	CP (HL)
	JR NC,.NextSort+1
.FAST:	LDI
	JP PO,.NextSort
	CP (HL)
	JP C,.FAST
	JP .NextSort

.EXIT	RET

; Example data:

DATAS:	DB 0,9,2,7,6,2,8,1,1,4
DATAE:
Страница 1/5
| 2 | 3 | 4 | 5