Section 22.11 Debugging QuickSort

Both programs below are supposed to implement QuickSort, but each has a bug that keeps it from correctly sorting the entire list. Run each one, compare the “Sorted array” output to what it should be, and find the mistake.

Activity 22.3. Debug 1.

This version doesn’t fully sort the array. What is missing?

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);
        quickSort(list, start, i-1);
    }
    else{
        return;
    }
}
void printArray(int list[],int n){
    int i;
    for(i=0; i<n; i++){
        printf("%d ", list[i]);
    }
    printf("\n");
}

Hint.

Look closely at how many times quickSort() calls itself inside its own body. A correct divide-and-conquer sort needs to recurse on both sides of the pivot.

Activity 22.4. Debug 2.

This version also fails to sort correctly, for a different reason. What is wrong this time?

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);
        quickSort(list, start+1, i-1);
        quickSort(list, i+1, end-1);
    }
    else{
        return;
    }
}
void printArray(int list[],int n){
    int i;
    for(i=0; i<n; i++){
        printf("%d ", list[i]);
    }
    printf("\n");
}

Hint.

Compare the arguments passed to the two recursive calls to quickSort() here with the version from the previous section. Which array elements are being excluded from further sorting that shouldn’t be?

Prev Top Next