Data Structures - Chapter 13 - Programming Assignment
Implementing a Simple Quicksort Function

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages

The Assignment:

You will implement and test the quicksort function. This simple implementation will sort an array of integers and follow the pseudocode from Chapter 13.

Purposes:

Ensure that you can implement the recursive pseudocode for quicksort.

Before Starting:

Read all of Chapter 13, especially pages 595-603.

Due Date:

________________

File that you must write:

1. quick1.h: Header file for this version of the quicksort function. You don't have to write much of this file. Just copy our version from quick1.h and add your name and other information at the top. NOTE: This header file contains only one prototype (for the quicksort function) and its documentation. It does not have any class declarations.
2. quick1.cxx: This file should contain the implementations of the simple quicksort function that is described in the header file.
3. makefile: This is a makefile for the assignment. The file should contain targets for qtest1.o, qexam1.o, qtest1 (an executable file) and qexam1 (another executable file). The source codes qtest1.cxx and qexam1.cxx are available in the locations listed below. Your makefile should also include "all" and "clean" options. Include your name in a comment at the top.

Other files that you may find helpful:

1. qtest1.cxx: A simple interactive test program.
2. qexam1.cxx: A non-interactive test program that will be used to grade the correctness of your quicksort function.

The Simple Quicksort Function
Discussion of the Assignment

There may be several functions in your quick1.cxx (such as the partition function). But quick1.h must only have ONE prototype (the prototype for the quicksort function). Any other functions that are in quick1.cxx should be declared with "internal linking". This hides the function name from the linker, and is accomplished by placing the word static before the function prototype and before the function definition. For example: static void partition(int data[ ], size_t n, size_t& pivot_index)...

The grading program will run at least these tests:

1. Calls quicksort(NULL, 0) to make sure that it doesn't crash.
2. Calls quicksort to sort an array with just one element.
3. Calls quicksort to sort an array with 1000 elements (containing the numbers 0 through 1000 in a random order). See Note 4 below. Check that the array is correct after sorting.
4. Calls quicksort to sort an array that contains 1000 elements with two copies of the numbers from 0 to 499. Check that the array is correct after sorting.
5. Calls quicksort to sort an array that contains the numbers 0 through 25 already sorted.
6. Calls quicksort to sort an array that contains the numbers 25 through 0 in reverse order.

Write the a precondition/postcondition contract for each function that you implement (such as partition). Put these contracts in your .cxx file.