From Citizendium
Jump to navigation Jump to search
This article is a stub and thus not approved.
Main Article
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
This editable Main Article is under development and subject to a disclaimer.

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²).


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;
            swap(c, r, size);
        } else
            c = (char*)c + size;
    c = (char*)c - size;
    swap(p, c, size);
    sort(p, left, size, compare);
    sort(p+right*size, num-right, size, compare);