CSE 378 Fall 2010 Homework 3

Due: Wednesda, October 20th at 5:00pm

The goal of this assignment is to learn about x86-64 functions and calling conventions.

Implementing Quicksort

For this assignment you'll write your old friend Quicksort - a recursive, in place, average-case O(NlogN) sorting routine - in assembly. Here's some pseudo-code for Quicksort for sorting an array of integers in a non-decreasing order:
void quicksort (integer A[], integer p, integer r) begin
  integer q;
  if p < r then
    q := partition(A, p, r)
    quicksort(A, p, q)
    quicksort(A, q+1, r)
  end if
end quicksort

integer partition (integer A[], integer p, integer q) begin
  integer pivot := A[p]
  integer i := p-1
  integer j := q+1
  while (true)
    repeat j := j-1 until (A[j] <= pivot)
    repeat i := i+1 until (A[i] >= pivot)
    if i < j then
      swap(A, i, j)
    else
      return j
    end if
  end loop
end partition

void swap (integer A[], integer i, integer j) begin
  integer temp := A[i]
  A[i] := A[j]
  A[j] := temp
end swap
The template calls Quicksort on an array of signed integers using the function signature in the pseudocode. We provide the swap function. Of course, you don't have to follow the pseudocode exactly so long as you implement Quicksort.

We will test your implementation on multiple arrays with interesting values. You may want to modify the array in the template to try other values. A component of your grade will also be based on your adherence to the Linux/Mac OSX AMD64 calling conventions, outlined in Week 2's section notes.

What you should do for this assignment:

  1. Start by downloading the template file (Mac version).

  2. Implement the body of the quicksort function and the entire partition function.

  3. Compile your program using the following command:
    gcc -o hw3 hw3-template.s
  4. Test your solution by executing the generated 'hw3' executable using the command:
    ./hw3
  5. Turn-in your completed assembly code file to the course's Catalyst CollectIt dropbox. Be sure you have commented your code as necessary to help your TAs give you as much partial credit as possible. Also ensure you've placed your name in the block of comments at the top of the file.