Quicksort

From Citizendium
Revision as of 01:56, 14 November 2010 by imported>Raymond Martineau (Create page (redlink from Algorithm))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
This article is a stub and thus not approved.
Main Article
Discussion
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²).

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