sorting routine in assembly for PIC

[Kaleborg]

Hello,
I have little difficulty with my routine for sorting list.

	sortit		
			btfsc	flag,0			;this is part of problem
			goto	cont
			bsf		flag,0
			movlw	0x30			;starts here
			movwf	FSR
seeifbig
			
			movf	INDF,W			;copy value to temp
			movwf	sTemp1
			incf	FSR,FILE		;copy next value
			movf	INDF,W
			subwf	sTemp1,W		;compare it
		;	bsf		flag,0
			btfss	STATUS,0		;if bigger or if zero... 
			goto	seeifbig
			btfsc	STATUS,2
			goto	sortit
			movf	INDF,W
			movwf	sTemp2			;...swap it
			movf	sTemp1,W		;
			movwf	INDF
			decf	FSR,FILE		;
			movf	sTemp2,W
			movwf	INDF
			incf	FSR,FILE
			;movf	FSR,W
			;subwf	flag,W	
			bcf		flag,0			;here is my problem
			goto	sortit
cont		return

My problem is that i'm not sure how to stop sorting. When list is sorted from the lowest value to the highest what should i do to make it jump out of that subroutine.
Please help
Regards

 

[Colbhaidh]

Is the list dynamic or do you always know how many items are to be sorted - then a counter can be added. If it is dynamic you could add a subroutine to count how many values are to be sorted before sorting.

 

[Kaleborg]

Thanks for reply.

There are 16 values in the list. But how i can determine how many times it will have to repeat sorting routine? Because if the values entered into the list are more less in order then routine has to be repeated only 3 times or 4 times but if list is really messy then it may take 50 repeats even.


Reagrds

 

[betwixt]

Use a flag bit.

Reset a bit each time you enter the sort loop. If you exchange bytes, set the bit.
When you reach the end, the bit will still be reset if you are finished.

Brian.

 

[Kaleborg]

Hello betwixt.
Thanks for reply.

This does not seems to be working for me. This flag way, i just cant seem to be able to use it in my code.

Would you be kind to look at my code and suggest what i should change?
his is my code after change.

sortit		btfss	flag,0			;check for flag, it is set before in code
			goto	ret		
			movlw	0x30			;starts here
			movwf	FSR

seeifbig
			bcf		flag,0			;reset a flag bit
			movf	INDF,W
			movwf	sTemp1
			incf	FSR,FILE		;copy next value
			movf	INDF,W
			subwf	sTemp1,W		;compare it
			btfsc	STATUS,2		;if 0 chek next value
			goto	seeifbig		; if not check if bigger
			btfss	STATUS,0		;if bigger swap
			goto	seeifbig		;if not coninue
			goto	swap
swap		
			bsf		flag,0           ;set flag
			movf	INDF,W
			movwf	sTemp2			;...swap it
			movf	sTemp1,W		;
			movwf	INDF
			decf	FSR,FILE		;
			movf	sTemp2,W
			movwf	INDF
			incf	FSR,FILE	
			goto	sortit			; go back and chec whole list again
ret			
			return

So it still does not jumps out fro the subroutine. And sometimes jumps out but without finishing sorting.

Regards

 

[betwixt]

I haven't had time to run it through a simulator but these are my initial ideas:

1. change the 'goto ret' line to 'return' - there is no need to jump to a return instruction. You can then remove the last two lines completely.

2. I can't see how it is supposed to know when the data it is sorting finishes, it will keep looping until possibly 256 bytes have been sorted. You need to specify a terminator value in your data table or tell it how many bytes there are to sort through.

3. Cosmetic changes, 'STATUS,2' should be "STATUS,Z' and 'STATUS,0' should be 'STATUS,C'. Similarly all references to 'FILE' should be to 'f'.

Try that out and let me know how you get on.

Brian.

 

[Kaleborg]

Hello betwixt.
Thanks for reply.

1. change the 'goto ret' line to 'return' - there is no need to jump to a return instruction. You can then remove the last two lines completely.

Done.

2. I can't see how it is supposed to know when the data it is sorting finishes, it will keep looping until possibly 256 bytes have been sorted. You need to specify a terminator value in your data table or tell it how many bytes there are to sort through.

Thats exactly what my problem is. Initially it was sorting ok. But then i noticed that when there were two same values beside each other it was stopping in infinite loop. So i add check if 0 line. Now it sorting quite well but dunno how to stop it after sorting. And you are right sometimes its keep sorting till the end of memory. I don't know how write that code differently. So now i'm desperate i just place bsf and bcf commands in different parts of code and hope that it'll be right.

3. Cosmetic changes, 'STATUS,2' should be "STATUS,Z' and 'STATUS,0' should be 'STATUS,C'. Similarly all references to 'FILE' should be to 'f'.

Done.

Regards

 

[betwixt]

I'm not a mathematician so someone please correct me if I'm wrong, I think the maximum possible number of iterations, assuming the table is initially in reverse order is 'n squared' where n is the length of the list being sorted.

So you could wrap the whole routine in a loop that ran either n² times or the flag stayed reset, whichever came first. Note that bubble sorts can be very slow !

Or, if you have a value that you know will never occur in your list, you could attach it to the end of the list and check for when you reach it.

Or, if the list is a known length, you could check to see if the FSR has reached it by comparing it with (0x30 + length) on each pass.

Brian.

 

[Kaleborg]

Hello Brian.

Thanks for reply and sorry for being pain in the a**.

I'm gonna try out these two suggestions:

Or, if you have a value that you know will never occur in your list, you could attach it to the end of the list and check for when you reach it.

Or, if the list is a known length, you could check to see if the FSR has reached it by comparing it with (0x30 + length) on each pass.

I already try first method but i wasn't working for me. Well it was working when list was messy but when data's were entered in more less ordered fashion sorting routine was overlapping onto higher addresses.

Thanks for that.

Regards

Added after 30 minutes:

Ok it works.

Thanks a million for help Brian. I've done it using 3rd way by checking address at FSR register.

sortit				
			movlw	0x30			;starts here
			movwf	FSR

seeifbig
			movf	FSR,W		;check address
			subwf	flag,W	
			btfsc	STATUS,Z	;to here
			return
			movf	INDF,W
			movwf	sTemp1
			incf	FSR,f		;copy next value
			movf	INDF,W
			subwf	sTemp1,W		;compare it
			btfsc	STATUS,Z		;if 0 chek next value
			goto	seeifbig		; if not check if bigger
			btfss	STATUS,0		;if bigger swap
			goto	seeifbig		;if not coninue
			goto	swap
swap		
			movf	INDF,W
			movwf	sTemp2			;...swap it
			movf	sTemp1,W		;
			movwf	INDF
			decf	FSR,f		;
			movf	sTemp2,W
			movwf	INDF			
			goto	sortit			; go back and chec whole list again

Here is the code if anybody would be ever interested.
To the flag variable you have to load address at which it should finish.