Quick Sort Implementation in C

Quicksort is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.Sorting_quicksort_anim

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting.
Mathematical analysis of quicksort shows that, on average, the algorithm takes O(nlogn) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare. [Wikipedia]

Here is implementation in C.

#include <stdio.h>

void quicksort(int a[], int left, int right);
int  partition(int a[], int left, int right);

int main(int argc, const char * argv[])
{
    int numbers[] = {5, 1, 0, 4, 2, 3};
    int size = sizeof(numbers)/sizeof(numbers[0]);
    int i;
    
    printf("unsorted:");
    for (i=0;i<size;i++) printf("%d ", numbers[i]);
    printf("\n");
    
    quicksort(numbers, 0, size - 1);
    
    printf("  sorted:");
    for (i=0;i<size;i++) printf("%d ", numbers[i]);
    printf("\n");
    
    return 0;
}


void quicksort(int list[], int left, int right)
{
    int pivotIndex;
    if ( left &lt; right)
    {
        pivotIndex = partition(list, left, right);
        quicksort(list, left, pivotIndex - 1);
        quicksort(list, pivotIndex + 1, right);
    }
}

int partition(int list[], int left, int right)
{
    int low, high, t, pivot;
    pivot = list[left];
    low = left;
    high = right + 1;
    while (low < high)
    {
        do ++low; while (list[low] <= pivot && low < right); 
        do --high; while (list[high] > pivot);
        
        if (low < high ) {
            t = list[low]; list[low] = list[high]; list[high] = t;
        }
    }
    
    t = list[left]; list[left] = list[high]; list[high] = t;
    
    return high;
}