quicksort in assembly for intel 8085

[kopun]

I ask for your help to write the quicksort algorithm in 8085 assembly. I tried to write it and of course it has too many bugs but my main problem is that I don't know how to handle the recursive character of the algorithm and control the loops. For example, what kind of flag should i use to know if the 1st partition is sorted so to call quicksort for the second partition? ( I used a simulator)
The dataset I used is 37 2 6 4 89 8 10 12 68 45 starting from memory position 3000H and regs bc: 1st element index/ de: last elem index
If u or anyone else could take a look, I would be thankful.

Here is my code:

;initialisation
LXI SP,FFF0H
LXI H,3009H
XCHG
MVI B,30H
MVI C,00H

QSORT:
MOV H,B
MOV L,C
MOV A,M
MOV L,E


SCANR:

CMP M
PUSH PSW
CNC SWAP
CPI 01H
JZ SCANL
DCX H
JMP SCANR



SCANL:
POP PSW
MOV C,L
LXI H,3000H

LOOP:
INX H
CMP M
PUSH PSW
PUSH B ;;;

CC SWAP
JZ RECURSIVE
CPI 01H
JNZ LOOP
POP H ;;;
POP PSW
JMP SCANR


SWAP:
PUSH B
PUSH D
PUSH H

MOV D,M
MOV L,C
MOV E,M
MOV M,D
POP H
MOV M,E
MVI A,01H
POP D
POP B
MOV C,L




RECURSIVE:


;BREAK



LXI B,3000H
DCX H
MOV E,L
JMP QSORT ; I<X

QS2:
LXI B,3009H

;BREAK

INX H
INX H
MOV E,L
JMP QSORT

HLT

the quicksort in c is:
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers

;
while (left < right)
{
while ((numbers

>= pivot) && (left < right))
right--;
if (left != right)
{
numbers

= numbers

;
left++;
}
while ((numbers

<= pivot) && (left < right))
left++;
if (left != right)
{
numbers

= numbers

;
right--;
}
}
numbers

= pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}​

 

[Salem]

Please use the [tt][ignore]

[/ignore][/tt] tags when posting code.

--

 

[zeitghost]

Gosh that was helpful...

Sadly, there's no sort listing in my 1985 8085 assembler book.

Or the Z80 book...

Sorry.

 

[kopun]

@ salem: I didn't know about that. sorry
@zeitghost: I don't think that there is such implementation. I once found the quicksort for Z80 but I couldn't understand it.
anyway thanx

 

[SimonSellick]

Could you add some comments to your implementation, please? It's a while since I used an 8085 (actually, a Z80) and it would help with understanding what you are trying to achieve (perhaps just put the equivalent 'C' source line at the start of each block of code?).

In general, and without wanting to tell you what you already know, you need to keep all the recursive stuff on the stack, and the easiest way to know when you have finished is to reserve one of the flags to tell you so (maybe z or c). If you actually code it with recursive calls (not jumps) then it will return to the caller on completion so unwinding the stack isn't an issue as long as the calls are well-behaved.

Hope this helps.

 

[zeitghost]

This particular question seems to appear in a remarkable number of places on the web...

 

[kopun]

After 5 months I decided to give another shot to this program. So I rewrote the partitioning process according to the c version on the first thread.(comments included!!)This part is fully functional and returns the pivot address in each 16-bit register. And then comes the recursive part....

1. How should I build the stack to preserve the parameters of each instance of q_sort and more important how retrieve the right parameters at the right time?
Suppose that every call of qsort produces 2 instances of itself. When the left partition is sorted, how is possible to backtrace the recursion tree, meaning going on the second call after the initial call to quicksort the right partition.

2. What's the difference of using jmp instuctions (in this program) instead of call, except the fact that a subroutine call pushes the address of the next instruction on the stack. If I use call instuctions, it seems that the function returns only when the sorting is done.

;*****INITIALIZATION*****
LXI SP,FFFFH
LXI B,3000H	;1st number location
LXI D,3007H ;Last number location
;MVI L,06H	; array size

CALL QUICKSORT
HLT

QUICKSORT:
PUSH PSW	;saving the CPU registers
PUSH B
PUSH D
PUSH H	
;***********************************
PUSH H	;pushing the quicksort
PUSH D	;initial parameters
PUSH B	;into stack (FFFA)


CALL q_sort



q_sort:	; subroutine q_sort takes the 
		;pointers to the first and last 
		;element as parameters and returns the pivot 
		; q_sort(BC,HL)
PUSH B	;push pointers
PUSH D
;MOV A,M	;PIVOT =1ST ELEM
LDAX B	;A <= (BC)
;while (left<right){
EXTLOOP:
;IS LEFT <RIGHT?
PUSH PSW	;save ACC
;MOV A,C	;16-bit compare subr. of memory locations
;CMP E		;IS LEFT <RIGHT?
XCHG
CALL COMPARE
JNC REC	;if not exit the external loop
;JNZ REC	;		-//-
POP PSW	;restore ACC
XCHG ;##################
;while (numbers[right]>= pivot && left<right
;{ pointers are BC and DE

SCAN_RIGHT:
;LDAX B	;A <= (BC)
MOV H,D	;DE=>HL
MOV L,E	;copying the pointer
;stc
;cmc
LOOP:
CMP M		;is the elem pointed by HL greater than ACC
JNC SWAP_CTRLR
PUSH PSW
;MOV A,C	;IS LEFT < RIGHT
;CMP L
CALL COMPARE
JNC SWAP_CTRLR
POP PSW
DCX H
JMP LOOP
;}
SWAP_CTRLR:
XCHG
PUSH PSW
MOV A,C
CMP E ;IF LEFT!=RIGHT
CC SWAP
JC LEFT_INC
POP PSW
JMP SCAN_LEFT
LEFT_INC:
POP PSW
INX B

;}

;while mumbers[left]<=pivot && ....
SCAN_LEFT:
MOV H,B	;BC => HL
MOV L,C
LOOP2:
CMP M
JC SWAP_CTRLL
PUSH PSW
MOV A,E	;IS LEFT < RIGHT %^&*()(&^%$$##
CMP L
MOV B,H ;HL=> BC
MOV C,L
XCHG
CALL COMPARE
XCHG
MOV H,B	;BC => HL
MOV L,C
JNC SWAP_CTRLL
POP PSW
INX H
JMP LOOP2

SWAP_CTRLL:
MOV B,H
MOV C,L
PUSH PSW
MOV A,C
CMP E ;IF LEFT!=RIGHT
CC SWAP
JC RIGHT_DEC
POP PSW
JMP EXTLOOP

RIGHT_DEC:
POP PSW
DCX D
JMP EXTLOOP;}


;recursive part
REC:
;BREAK
POP PSW
POP PSW

POP D
POP B
PUSH B
PUSH D
PUSH H
;BREAK


;IF LEFT < PIVOT ADDRESS CALL Q_SORT(left,pivot-1)
CALL COMPARE	;compare(BC,HL)
JNC REC2
;PUSH H
;PUSH D
;PUSH B
DCX H
XCHG
JC Q_SORT

REC2:
;IF right>PIVOT ADDRESS CALL Q_SORT(pivot+1,right))
;BREAK

XCHG
CALL COMPARE
INX H
MOV B,H
MOV C,L
JC Q_SORT


;BREAK


POP H
POP D
POP B
POP PSW
RET ;return to main program 


SWAP:	;swap elements pointed by BC and DE
PUSH PSW
PUSH B
PUSH D
PUSH H
LDAX B
XCHG
MOV E,M
MOV M,A
MOV H,B
MOV L,C
MOV M,E
POP H
POP D
POP B
POP PSW
RET

;compares bc and hl values(16-bit) 
COMPARE:
STC
CMC
MOV A,B
CMP H
JNZ SET
MOV A,C
CMP L
JC LESS ;B<H
JNC GREATER
SET:
JC LESS ;B<H
JNC GREATER ;B>H
LESS:
STC
RET
GREATER:
STC
CMC		
RET

 

[lionelhill]

... well, it's all very educational, but if you're going to do it exactly like C would, why not just use a C implementation anyway? There are thousands of them out there.

 

[kopun]

It is indeed for educational purposes...and practical reasons because the hex file that derives from the C code is about 40K.

The point is to understand how the recursion works at low level and particularly how the stack is built.

 

[lionelhill]

... ah, then if for educational purposes, I suggest you use your version in C, compile it, and disassemble the result. That will show you how a C-compiler handles recursion, storage of local variables and parameters. In fact you might even prefer to use some really trivial algorithm rather than quicksort so there's less code to search through looking for the starts and ends of function calls. There are also usually good chapters in assembly books on integration with high level languages; these cover the stack structures and calling methods.