[x]
Posted via EE Mobile

Search, ask, and monitor your questions on the go with EE Mobile. Visit Experts Exchange from your mobile device and never be out of touch again.

05/30/2009 at 10:55PM PDT, ID: 24451228 | Points: 500
[x]
Attachment Details

Need assembly code for non-recursive quick sort

Asked by gonesr in Assembly Programming Language, C Programming Language

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.pdf

The 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.

[+][-]05/31/09 10:24 AM, ID: 24513225

At Experts Exchange, members can ask their questions to thousands of technology professionals, also known as Experts. Experts compete and collaborate to answer those questions by leaving comments like this one.

Start your 30-day free trial to view this Expert Comment or ask the Experts your question.

 
[+][-]05/31/09 10:27 AM, ID: 24513237

At Experts Exchange, members can ask their questions to thousands of technology professionals, also known as Experts. Experts compete and collaborate to answer those questions by leaving comments like this one.

Start your 30-day free trial to view this Expert Comment or ask the Experts your question.

 
[+][-]05/31/09 01:05 PM, ID: 24513726

Often, when Experts are collaborating with members who have asked questions, they will request additional information about the problem. Askers respond with an author comment like this one.

Start your 30-day free trial to view this Author Comment or ask the Experts your question.

 
 
Loading Advertisement...
20091028-EE-VQP-86 - Hierarchy / EE_QW_3_20080625