Worst Cases of QuickSort
Ramprasad Joshi
February 2, 2016
Abstract
In this article, we look at the worst cases of QuickSort: what they are, and how numerous they are. We assume that the pivot is always picked up from the first element.

1

The Plan

We run the following program repeatedly:
#include<stdio.h>
#include<stdlib.h> int Partition(int *A, int l, int r, int *count) { int i = l, j; for(j = l+1; j <= r; j++) {
(*count)++;
if(A[j]<A[l]) { i++; int temp; temp = A[j];
A[j] = A[i];
A[i] = temp;
}
} int temp; temp = A[l];
A[l] = A[i];
A[i] = temp; return i;
}
void QuickSort(int *A, int l, int r, int *count) { if(l < r) { int pivot; pivot = Partition(A, l, r, count);
QuickSort(A, l, pivot-1, count);
QuickSort(A, pivot+1, r, count);
}
}
1

void NextAssignment(int n, int *B) { int i; for(i = 0; i < n; i++) {
B[i] = 1 - B[i]; if(B[i]) break;
}
} int main(int argc, char *argv[]) { printf( "This program seeks to print all possible worst cases for QuickSort\n"); printf( "for the elements {1,2,...,n}\n"); printf( "Usage ./%s <n>. n defaults to 8\n", argv[0]); int n = 9; if(argc > 1) { n = atoi(argv[1]); if(n < 5) n = 5; if(n > 20) printf("n=%d too large. Prepare to get flooded.\n", n);
}
int i, A[n], B[n], C[n]; for(i = 0; i < n; i++) {
A[i] = i+1;
B[i] = 0;
}
for(i = 0; i < (1 << n); i++) { int j, l, h; l = 0; h = n-1; for(j = 0; j < n; j++) printf("%d ",C[j]=(B[j]?A[l++]:A[h--])); int count; count = 0;
QuickSort(C, 0, n-1, &count); for(j = 0; j < n-1; j++) if(C[j]>C[j+1]) { printf("QuickSort error!\n"); break; } printf(": Comparison Operations %d\n", count);
NextAssignment(n, B);
}
printf( "Were all worst cases? Were all worst cases covered?\n"); return 0;
}

2

Execution

Run the following shell command sequence, after compiling the abovelisted program to a.out: $ for ((i=4; i<=20; i++)) ; do ((j=i*(i-1)/2)) ; echo $i ‘./a.out $i | awk ’{print $NF;}’ | grep -c $j‘ ; done
Get the quotes right in the foregoing. Study and explain the output.

2