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.

Purposes:

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

     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.

How a Program Can Use the Flexible Quicksort Function

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

    #define element(i) (base + ((i)*bytes))
    #define assign(x,y) (memcpy((x), (y), bytes))
    #define less_than(x,y) (compar((x),(y)) < 0)

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

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

        static
        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

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:
   • Pop a size n and a starting index i off the stack. We must now sort the n-element array segment starting at element(i). If n is less than 16 then you can accomplish the sort by simply calling:
     insertion_sort(element(i), n, bytes, compar);
     On the other hand, if n is 16 or more, then you must proceed with the following two steps...
   • Partition the n-element array segment starting at element(i). After the partition, you should have a local variable called pivot_index indicates where the pivot element ended up.
   • The n-element array segment starting at element(i) has now been broken into two smaller pieces--the piece before the pivot and the piece after the pivot. From these two pieces, figure out which one is bigger. Push the size and starting position of this bigger piece onto the stack (so that we'll deal with it later). Then push the size and starting position of the smaller position onto the stack (so that we'll also deal with it!)