Programming Puzzles

Write a routine to implement the "pivot" stage of a QuickSort. Your routine will take an unsorted array, the index of the element to pivot around, and will rearrange the array so that the elements smaller than the pivot element come first, larger come after, and equal to are clustered in between. It will also return the locations of the first and last elements equal to the pivot.

Remember, routines that are submitted without being tested and yet still pass will get much more kudos. Please indicate in comments in your code how much testing you have done.

The Specification

Your routine should be declared as follows:

  void pivot( void *array,
              int   array_size,
              int   pivot_index,
              int (*cmp)(void *, int, int),
              int (*swp)(void *, int, int),
              int   temp_index,
              int  *ptr_to_first,
              int  *ptr_to_last
            );

In this prototype the arguments are as follows:

• void *array
  An array of elements of unknown type. You know nothing more about these. This is passed as the first parameter to the functions cmp and swp.
  
  
• int array_size
  The number of elements in the array. The array is indexed from 0, so that if 0 <= i < array_size then element array[i] exists.
  
  
• int pivot_index
  This is the index of the element about which you will be pivoting.
  
  
• int (*cmp)(void*,int,int)
  This function will compare two elements of the array and return -1, 0, or 1. Conceptually,
  • A[i] < A[j] implies cmp(i,j) = -1
  • A[i] = A[j] implies cmp(i,j) = 0
  • A[i] > A[j] implies cmp(i,j) = 1
  
  
• int (*swp)(void*,int,int)
  This function swaps two given elements of the array.
  
  
• int temp_index
  Since you don't know the type of the objects in the array, you can't declare temporary variables of that type. The element array[temp_index] can therefore be assumed to exist and be empty. Thus it can be used as temporary storage.
  
  
• int *ptr_to_first
  This is where to store the index of the first element that compares as equal to the pivot after the routine finishes.
  
  
• int *ptr_to_last
  This is where to store the index of the last element that compares as equal to the pivot after the routine finishes.
  
  

The function cmp passed in to routine pivot is your only means of comparing two elements, and the function swp is your only means of moving entries.