Quicksort: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Raymond Martineau
(Create page (redlink from Algorithm))
 
imported>Meg Taylor
(move links to subgroup)
 
Line 41: Line 41:
}
}
</pre>
</pre>
== External links ==
* [http://comjnl.oxfordjournals.org/content/5/1/10.full.pdf+html Quicksort] by C. A. R. Hoare. The Computer Journal (1962) 5 (1): 10-16

Latest revision as of 09:18, 14 September 2013

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);
}