Hi, I have written the following assembly code for recursive quick sort which uses calling QUICK SORT function to sort the right and left branches.
LEA R0, Start Address
LEA R1, End Address
CALL QUICK SORT
HLT
QUICK SORT PUSH R1
PUSH R0
SUB R0, R1
BRn LABEL
RET
LABEL LDI R2, R0, #0
AND R4,R2,R2(Moving the pivot element to R4)
LABEL1 INCR R0
LDI R2,R0,#0
SUB R5,R4,R2
BRnz LABEL2
BR LABEL1(R2 will have the element greater
than the pivot element)
LABEL2 SUB R5,R0,R1
BRnz LABEL4
LDI R3,R1, #0
DECR R1
SUB R5,R2,R3
BRnz LABEL2(R3 will have the element less
than the pivot element)
LD R5,R1,#0
STI R2,R1,#0
STI R5,R0,#0
BR LABEL1
LABEL 4 LD R5,R1,#0
LDI R4,R1,#0
POP R0
STI R5,R0,#0
INCR R1
PUSH R1
DECR R1
DECR R1
CALL QUICK SORT
POP R0
POP R1
CALL QUICK SORT
RET
I want a non-recursive code which doesn't call QUICK SORT at all for sorting the right and
left branches.I don't want PUSH/POP/SUB instructions in the code.Also it would be great if the assembly code used comprises the LC3 ISA.
Link to LC3 ISA is
http://highered.mcgraw-hill.com/sites/dl/free/0072467509/104653/PattPatelAppA.pdfThe probable C code for the non-recursive quick sort is :
void quicksort(Item * a, int start, int stop)
{
int i, s = 0, stack[64];
stack[s++] = start; stack[s++] = stop;
while (s > 0)
{
stop = stack[--s]; start = stack[--s];
if (start >= stop) continue;
i = partition(a, start, stop);
if (i start > stop i)
{
stack[s++] = start; stack[s++] = i - 1;
stack[s++] = i + 1; stack[s++] = stop;
}
else
{
stack[s++] = i + 1; stack[s++] = stop;
stack[s++] = start; stack[s++] = i - 1;
}
}
}
----------
The partition function looks like :
int partition(Item * a, int start, int stop)
{
int up = start, down = stop 1, part = a[stop];
if (stop <= start) return start;
while (true)
{
while (isLess(a[up], part))
up++;
while (isLess(part, a[down]) && (up < down))
down--;
if (up >= down) break;
Exchange(a[up], a[down]);
up++; down--;
}
Please let me know if I'm not clear.
Thanks in advance.