Quicksort

Quicksort is a sorting algorithm developed by C. A. R. Hoare.

This algorithm operates by selecting a pivot value within the elements to be sorted, with the remaining elements divided into two groups indicating whether they are greater than or less than the pivot value. After moving the pivot value between the two separated groups, the quicksort algorithm is recursivly performed on the smaller groups.

In normal circumstances, the efficiency of Quicksort is O(n log n). In the worst case scenario, it is O(n²).

Implementations

The following is an implementation of quicksort in C:

void sort(void *p, size_t num, size_t size, int (*compare)(const void *, const void*))
{
    int right=num;
    int left=1;
    void *c=((char*)p)+size;
    void *r=((char*)p)+right*size;
    int i;

    if (num<=1) return;
     
    while (left<right)
    {    
        if (compare(c, p)>0)
        {
            r = (char*)r - size;
            --right;
            swap(c, r, size);
        } else
        {
            ++left;
            c = (char*)c + size;
        }
    }
    --left;
    c = (char*)c - size;
    swap(p, c, size);
    
    sort(p, left, size, compare);
    sort(p+right*size, num-right, size, compare);
}

External links

• Quicksort by C. A. R. Hoare. The Computer Journal (1962) 5 (1): 10-16