Quickselect

Animated visualization of the Quickselect algorithm. Selection of the 22nd smallest value.

Quickselect ( English quick , German 'quickly' and to select 'select') is a selection process from computer science to find the k-smallest element in an unordered list. It refers to the quick sort - sort algorithm . Like Quicksort, it was developed by Tony Hoare and hence is also known as the Hoare selection algorithm. Like Quicksort, it is efficient in practice and has a good average case , but also poor worst-case performance . Quickselect and its variants are the most commonly used selection algorithms in efficient practical implementations.

Quickselect takes the same overall approach as Quicksort, choosing one item as the pivot and dividing the data into two parts based on the pivot, smaller or larger than the pivot, respectively. However, instead of returning to both pages, as with Quicksort, the quick selection only returns to one page - the page with the item you are looking for. This reduces the average complexity from to , with a worst case of . ${\ displaystyle {\ mathcal {O}} (n \ log (n))}$ ${\ displaystyle {\ mathcal {O}} (n)}$ ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

As with Quicksort, the quick selection is generally implemented as an in-place algorithm , and beyond the selection of the k'th element, it also partially sorts the data.

principle

In Quicksort there is a subprocedure called partition that can, in linear time, group a list (left to right) into two parts: those that are less than a certain element and those that are greater than or equal to the element. Here is pseudocode that executes a partition over the item list [pivotIndex]:

Funktion partition(Liste, links, rechts, pivotIndex)
     pivotWert := Liste[pivotIndex]
     swap Liste[pivotIndex] und Liste[rechts]  // Pivot ans Ende verschieben
     speicherIndex := links
     für i von links bis rechts-1
         falls Liste[i] < pivotWert
             swap Liste[speicherIndex] und Liste[i]
             inkrementiere speicherIndex
     swap Liste[rechts] und Liste[speicherIndex]  // Pivot an die finale Stelle verschieben
     return speicherIndex

This is known as the Lomuto partition scheme , which is simpler but less efficient than Hoare's original partition scheme.

In Quicksort we sort both branches recursively, which leads to an optimal time. However, when making the selection, we already know which partition our desired item is in, as the pivot is in its final sorted position, with everyone preceding it in an unsorted order and everyone following it in an unsorted order. Therefore, a single recursive call finds the desired element in the correct partition, and based on this, the Quickselect algorithm is created: ${\ displaystyle {\ mathcal {O}} (n \ log n)}$

// Gibt das k-kleinste Element der Liste zurück inklusive Rechts-/Linkselement
// (z.B. links <= k <= rechts).
// Der Speicherbedarf des Datenfelds der Suche ändert sich mit jeder Rund, aber die Liste
// behält immer die gleiche Größe. Deswegen muss der Wert k nicht jede Runde aktualisiert werden.
Funktion auswählen(Liste, links, rechts, k)
     falls links = rechts        // falls Liste nur ein Element enthält,
         return Liste[links]  // return dieses Element
     pivotIndex  := ...     // Auswahl eines Pivotelements zwischen links und rechts,
                            // z.B., links + floor(rand() % (rechts - links + 1))
     pivotIndex  := partition(Liste, links, rechts, pivotIndex)
     // Pivot in seiner endgültigen sortierten Position
     falls k = pivotIndex
         return Liste[k]
     sonst falls k < pivotIndex
         return auswählen(Liste, links, pivotIndex - 1, k)
     sonst
         return auswählen(Liste, pivotIndex + 1, rechts, k)

Note the similarity with quicksort: Just as the minimal-based selection sort is a partial selection sort, this is a partial quicksort in which only its partitions are created and partitioned. This simple method has an expected linear run time and, like Quicksort, performs reasonably well in practice. It's also an in-place algorithm that only requires constant memory overhead when tail recursion optimization is available, or when tail recursion is eliminated with a loop: ${\ displaystyle {\ mathcal {O}} (\ log (n))}$ ${\ displaystyle {\ mathcal {O}} (n)}$

Funktion auswählen(Liste, links, rechts, k)
     loop
         falls links = rechts
             return Liste[links]
         pivotIndex := ...     // Auswahl PivotIndex zwischen links und rechts
         pivotIndex := partition(Liste, links, rechts, pivotIndex)
         falls k = pivotIndex
             return Liste[k]
         sonst falls k < pivotIndex
             rechts := pivotIndex - 1
         sonst
             links := pivotIndex + 1

Time complexity

Like Quicksort, the Quickselect has a good average performance but is sensitive to the pivot chosen. If good pivots are chosen, i. H. those that consistently reduce the search rate by a certain fraction, then the search rate decreases exponentially and by induction (or summation of the geometric series) one sees that the performance is linear, since every step is linear and the total time is a constant time ( depending on how quickly the search rate decreases). However, if bad pivots are consistently chosen, such as For example, the reduction of only a single element, then the worst-case performance is square: . This happens e.g. B. when searching for the maximum element of a set, where the first element is used as a pivot and the data is sorted. ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$

Individual evidence

^ CAR Hoare: Algorithm 65: find . Ed .: Communications of the ACM. Volume 4, Issue 7, July 1961, pp. 321-322 ( acm.org ).

[1] CAR Hoare: Algorithm 65: find . Ed .: Communications of the ACM. Volume 4, Issue 7, July 1961, pp. 321-322 ( acm.org ).