Quicksort is an "in place" and very efficient sorting algorithm based on the divide et impera technique. The steps are:

1. Divide: you partition the array in two subarrays around an element called "pivot", such as the left subarray contains the elements smaller (or equal) than the pivot, and the right one the greater elements.

2. Impera: you recursively sort these subarrays.

3. Combine: nothing.

The partition routine has linear time. The pivot is always the first element; the invariant is that at every iteration, before the index i there are smaller elements, before i and j an area S with greater elements, and after j an unknown part.

When an integer smaller than the pivot is encountered, it is swapped before i and the S area is "moved" right. At the end, the pivot is moved to the right location in order to divide the two sections, and its index is returned to the caller.

The Quicksort routine is then called again on the two subarrays. The base case is implicit, when a void array is passed to the routine.

Let's analyze the complexity in three cases: best case, worst case and a random case.

- Worst case: sorted or reverse sorted input (a subarray is void).

T(n) = T(0) + T(n-1) + Theta(n) where Theta(n) is the partition's cost. Solving the recurrence with the tree, we find T(n) = Theta(n²), no better than many others.

- Best case: array always divided exactly in half.

T(n) = 2T(n/2) + Theta(n) = Theta(n * logn) for the master theorem. Good!

- Random case: let's assume the partition is always 1/10 and 9/10.

T(n) = T(1/10) + T(9/10) + Theta(n). We find T(n) = Theta(n * logn).

We want to be "usually lucky" and have a good running time. So we may need an algorithm which is totally independent from the input form. For this scope, the programmer can randomly rearrange the elements before sorting or randomly choose the pivot. So no specific input can elicit the worst case!

But I'm not doing this because I wanted to realize a simple code.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include <stdio.h> #define SIZE 10 void printArray(int[]); int partition(int[], int, int); void swap(int[], int, int); void quicksort(int[], int, int); int main(int argc, char **argv) { int v1[SIZE] = {5, 2, 7, 10, 4, 9, 1, 8, 3, 6}; printf("Before sorting: "); printArray(v1); quicksort(v1, 0, SIZE); printf("After sorting: "); printArray(v1); } void printArray(int V[]) { int i; for (i = 0; i < SIZE; i++) { printf("%d ", V[i]); } printf("\n"); } /* * Routine to partition the array V[p...q] around the pivot V[p] * in linear time * Returns the pivot index */ int partition(int V[], int p, int q) { int pivot = V[p]; int i = p; int j; for (j = p+1; j <= q; j++) { if (V[j] <= pivot) { i++; swap(V, i, j); } } swap(V, p, i); return i; } /* * I can't use the XOR swapping here because sometimes * an element is swapped with itself and that would produce zero */ void swap(int v[], int index1, int index2) { int temp = v[index1]; v[index1] = v[index2]; v[index2] = temp; } void quicksort(int V[], int p, int q) { if (p < q) { int r = partition(V, p, q); quicksort(V, p, r-1); quicksort(V, r+1, q); } }