Data Structures - Chapter 13 - Advanced Programming Assignment
Implementing an Advanced 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 a flexible quicksort function that is based on the quicksort function in the C++ standard library.
Ensure that you can use pointer arithmetic in a fairly complex setting.
Before Starting:
Implement the ordinary quicksort function from Section 13.2 to ensure that you understand the algorithm. Also, review pages 459-463 (discussing how a function can be a parameter). Also read Exercise 8 on page 604 and Project 4 on page 617.
Due Date:
File that you must write:
  1. quick2.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 ~main2270/programs/quick2.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. quick2.cxx: This file should contain the implementations of the flexible quicksort function that is described in the header file. Make sure that you read all of the discussion below which describes special aspects of the programming.
  3. makefile: This is a makefile for the assignment. The file should contain targets for qtest2.o, qexam2.o, qtest2 (an executable file) and qexam2 (another executable file). The source codes qtest2.cxx and qexam2.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. qtest2.cxx: A simple interactive test program.
  2. qexam2.cxx: A non-interactive test program that will be used to grade the correctness of your quicksort function.

The Flexible Quicksort Function
Discussion of the Assignment

The Function's Specification

You will be writing a function with this specification:
     void quicksort(
         void* base,
         size_t n,
         size_t bytes,
         int compar(const void*, const void*)
     Precondition: base is a pointer to the first component of an array
     with at least n elements. The component type of the array may be
     any type at all, and the parameter bytes must be the number of bytes
     in each component of the array. The fourth parameter, compar, must
     be the name of a function that can compare two elements of the
     array. The two arguments of compar are pointers to two elements in
     the array, and the return value of compar indicates which of the
     two arguments is largest, as follows:
       -- a negative return value means that the 2nd argument is larger
       -- a zero return value indicates that the arguments are equal
       -- a positive return value means that the 1st argument is larger
     Postcondition: The elements of the array have been rearranged so
     that they are in order from smallest to largest.
This specification includes several new items that you haven't seen before, such as the third parameter (which must be the number of bytes required by one component of an array) and the fourth parameter (where the actual argument must be a function that you write and make available to the quicksort function).

How a Program Can Use the Flexible Quicksort Function

In order to understand the flexible quicksort function, you should start by fully understanding how a program can use this function to sort any kind of array. For example, the function can sort an array of integers, or sort an array of strings, or sort an array of doubles... The steps required in the program are as follows:
  1. The program must declare a comparison function that compares two elements from the array. For example, suppose that the program wants to sort an array of integers. Then that program must declare a comparison function that can compare two integers, as shown here:
         int compare_ints(const void* ptr1, const void* ptr2)
    	 // NOTE: *ptr1 is the first integer, but since ptr1 is a void
    	 // pointer, we must use the notation *((int *) ptr1) to refer to
    	 // this first integer. Similarly, *((int *) ptr2) refers to the
    	 // second integer. This comparison function works by subtracting
    	 // the second integer from the first, and returning the result.
    	 // This result meets the requirements listed above (for example,
    	 // it is negative when the second argument is larger than the
    	 // first.
    	 return *((int *) ptr1) - *((int *) ptr2);
    Notice that compare_ints has two parameters that are declared as void pointers. This means that in the prototype, we are not going to tell the compiler exactly what ptr1 and ptr2 are pointing to. But, as the implementor of this function, we know that ptr1 and ptr2 are actually pointing to integers. In particular:
    *((int *) ptr1) is the integer that ptr1 points to, and
    *((int *) ptr2) is the integer that ptr2 points to.
    The return value of compare_ints tells us whether the two integers are equal (return value of zero), or the first integer is bigger (return value is positive), or the second integer is bigger (return value is negative).
  2. Once you have your compare_ints function in place, the program you can declare an array of integers, and use quicksort to sort the array, as shown here:
         int my_numbers[4000];
         ...code to put 4000 numbers into the array my_numbers...
         // Now use quicksort. Note that the array my_numbers is the first
         // argument (but we need to cast it to void* to match the quicksort
         // prototype). The second argument is the number of elements in the
         // array. The third argument is the number of bytes in each array
         // component (obtained by using the predefined sizeof operator).
         // The fourth arguement is the comparison function listed above.
         quicksort((void *)my_numbers, 4000, sizeof(int), compare_ints);

Some Macros for the Flexible Quicksort Function

I suggest that you declare these "macro definitions" at the top of your implementation file:
    #define element(i) (base + ((i)*bytes))
    #define assign(x,y) (memcpy((x), (y), bytes))
    #define less_than(x,y) (compar((x),(y)) < 0)
The macros act sort of like functions, allowing you to easily access and manipulate elements of the array (even though you don't know the data type of that array!) You may use the macros in any place that has access to the quicksort parameters (base, bytes, and compar). Here is what the macros will do:
  1. For any index i in the range 0 to n-1, element(i) provides a pointer to element i of the array.
  2. If x and y are pointers to elements, then assign(x,y) makes the element that x points to be a copy of the element that y points to (sort of like *x = *y).
  3. If x and y are pointers to elements, then less_than(x,y) will be true if x's element is less than y's element.

Programming Techniques Inside the Partition Function

There are several programming techniques that you will find useful in your new implementation of the partition function.
  1. The partition function will need parameters for base, n, bytes and compar. It also needs the pivot_index as a reference parameter. Just like the earlier version, the partition function sets pivot_index equal to the index where the pivot element ends up.
  2. Within your partition function, you will need to declare memory that can hold a copy of the pivot element (from the [0] element of the array). You'll also need some memory to use as a temporary location during the swapping of two elements. I suggest that you allocate dynamic memory for these two purposes by using the malloc function from malloc.h. The correct syntax for the allocation is:
    void *pivot = malloc(bytes);
    void *temp = malloc(bytes);

    After these statements, pivot is a pointer to some memory that you can use to hold a copy of the pivot element, and temp is a pointer to some memory that you can use temporarily during the swapping of two elements.
  3. Example code to copy the [0] element to the memory that pivot points to:
    assign(pivot, element(0)); By the way, you could also use base instead of element(0).
  4. Example code to swap element i with element j using the temporary memory location:
    assign(temp, element(i));
    assign(element(i), element(j));
    assign(element(j), temp);
  5. It is a bad idea to always use the [0] element as the pivot (see the analysis on page 601). A better idea is to select a random element, somewhere between index [0] and index [n-1], and swap this randomly selected item with the [0] element at the start of the partition. Here's the code to do this, using the rand function from stdlib.h:
    size_t random_index = rand( ) % n;
    assign(temp, element(0));
    assign(element(0), element(random_index));
    assign(element(random_index), temp);

    After the swap, the partition can proceed as usual, using the new element from index [0] as the pivot.
  6. When the partition finishes, it must return the pivot and temp memory to the heap. The correct syntax for the returns are:
    free (pivot);
    free (temp);
    Notice that you are using free instead of delete. The reason is because the memory was originally allocated with malloc instead of new.

Using Insertion Sort When the Array Gets Small

Read Exercise 8 on page 604. Because of the discussion shown here, I'd like you to modify quicksort a bit. When the array reaches 15 or fewer elements, you should call an insertion sort to finish the work. You may use the implementation of insertion sort shown here:
        void insertion_sort(
            void* base,
            size_t n,
            size_t bytes,
            int compar(const void*, const void*)
            void *new_item = malloc(bytes);
            size_t i;
            size_t j;
            for (i = 1; i < n; i++)
            {   // Insert element i into the right place
                assign(new_item, element(i));
                for (j = i; (j > 0) && (less_than(new_item, element(j-1))); j--)
                    assign(element(j), element(j-1));
                assign(element(j), new_item);
            free (new_item);

Eliminating Recursion in Quicksort

Read Programming Project 4 on page 617. Your new implementation of quicksort should follow the plan shown there to eliminate the recursion. (If you have the first printing of the book, there is a bug in steps 2b and 2c of Project 4. The correction is available over the web. Because of the use of insertion sort (described above), the actual pseudocode for your new quicksort is modified a bit, as shown here:
  1. Push 0 and n onto the stack (indicating that we must sort the n-element array segment starting at element(0).
  2. while the stack is not empty:
Use the Stack template class from stack1.h and stack1.template: in your implementation (instantiating the Stack's item as size_t).

Michael Main (