Quickselect

From Wikipedia, the free encyclopedia

In computer science, quickselect is an algorithm to select the n^th smallest element of an array, based on the quicksort algorithm. For applications, see Order statistics.

Contents 1 The algorithm 2 Implementation 3 Complexity 4 See also 5 References

[edit] The algorithm

Like quicksort, quickselect applies a divide-and-conquer strategy to find the n^th smallest element by dividing the list of elements in the array into two sublists.

The steps are:

1. Pick any element from the array A. This element is called the pivot element.
2. Reorder the array A such that all elements that are less than the pivot go to the left of it, and all values that are larger go to the right of it. Elements which are identical to the pivot can be put on either side. This step is called the partition step which is also central to the Quicksort algorithm.

We will call the elements to the left of the pivot A₁ and the elements to the right of the pivot A₂.

1. If the number of elements of A₁ is exactly n-1, return the pivot element as the n^th smallest element.
2. If the size of A₁ is less than n-1, let k be the size of A₁ together with the pivot element, i.e. the size of A₁ plus 1, and apply this algorithm recursively to A₂ to find the n-k^th largest element.
3. If the size of A₁ is greater than n-1, apply the algorithm recursively to A₁ to find the n^th largest element.

If we are looking for the smallest element in a one-element array, this algorithm will pick this element as pivot. Since the size of A₁ will be zero, this returns the pivot as smallest element.

Now, if we are looking for the n^th largest element in an array with k elements, we can reorder this array as follows: We choose a pivot element as above and partition the array. If the number of elements that are smaller than the pivot elements is n-1, it will be at position n now, and therefore the n^th smallest element. On the other hand, if there are less than n-1 smaller elements, we find that the pivot element must be the m^th smallest element, thus we continue looking for the n-m^th smallest element in those that are bigger. Finally, if there are at least n elements that are smaller than the pivot, the n^th smallest is among them.

Since the size of the arrays in which the search is conducted is always decreased by at least one in each recursive call, this algorithm always terminates.

[edit] Implementation

A simple pseudo-code implementation may look like this:

function quickselect(n,A)
    var list less, greater
    if (n > length(A) or n < 1)
        return that there is no such element
    if (length(A) = 1 and n = 1)
        return the first element of A
    select a pivot value pivot from A
    for all elements x of A except pivot
        if x < pivot
            add x to less
        else
            add x to greater
    if length(less) > n-1
        return quickselect(n,less)
    else if length(less) < n-1
        return quickselect(n-length(less)-1,greater)
    else
        return pivot

[edit] Complexity

The worst-case time complexity for this algorithm is O(n²) for an array with n elements: If we want to find the smallest element and always choose the currently-largest element as pivot, we call the partition step n − 1 times, and this step takes O(n) time.

[edit] See also

• BFPRT

[edit] References

• Paul E. Black, Select at the NIST Dictionary of Algorithms and Data Structures.
• Schöning, U.: Algorithmik. Spektrum, 2001. ISBN 3-8274-1092-4. Page 126 in section 2.7: Selektionsalgorithmen.