QuickSort with Characters, and a Smarter Pivot

Section 22.12 QuickSort with Characters, and a Smarter Pivot

QuickSort doesn’t just work on numbers— as long as we have a way to compare two elements, we can sort anything. Let’s practice with an array of chars.

We’ll also address a weakness of the version of QuickSort we’ve used so far: always choosing the last element as the pivot works fine on average, but performs poorly when the list is already sorted (or nearly sorted), since the partitioning barely shrinks the list each time. A common fix is to use the median-of-three strategy: instead of always taking the last element, take the median of the first, last, and middle elements of the (sub)list as the pivot.

The two animations below start from the same, already-sorted list, side by side— one always pivoting on the last element, the other using median-of-three. Watch how much more work the plain version has to do:

Activity 22.5.

Starting from the working (integer) QuickSort below, modify the code to:

Sort the array of characters 'l','a','e','o','s','p','g','i' instead of an array of integers.
Before partitioning, swap whichever of the first, last, and middle elements is the median of the three into the last position, so that value is used as the pivot.

Compile and run the code below in your own C environment.

#define SIZE 8
#include<stdio.h>
void printArray(int list[],int n);
void quickSort(int list[], int start, int end);
int partition(int list[], int start, int end);

int main(void) {
    
    int list[] = {20,5,8,47,35,2,78,24}; /* unsorted numbers */
    printf("Unsorted array\n");
    printArray(list,SIZE);
    quickSort(list,0, SIZE-1);
    printf("Sorted array\n");
    printArray(list,SIZE);

	return 0;
}
int partition(int list[], int start, int end){
    int i, j, pivot, swap;
    pivot = list[end];
    i = start - 1;
    for(j=start; j<end; j++){
        if(list[j]<pivot){
            i++;
            swap = list[i];
            list[i] = list[j];
            list[j] = swap;
        }
    }
    i++;
    swap = list[end];
    list[end] = list[i];
    list[i] = swap;
    printArray(list,SIZE);
    return i;
}
void quickSort(int list[], int start, int end){
    int i;
    if(end>start){
        i = partition(list, start, end);

        //sort left part
        quickSort(list, start, i-1);

        //sort right part
        quickSort(list, i+1, end);
    }
    else{
        return;
    }
}
void printArray(int list[],int n){
    int i;
    for(i=0; i<n; i++){
        printf("%d ", list[i]);
    }
    printf("\n");
}