|
In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list. It is related to the quicksort sorting algorithm. Like quicksort, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient in practice and has good average-case performance, but has poor worst-case performance. Quickselect and variants is the selection algorithm most often used in efficient real-world implementations. Quickselect uses the same overall approach as quicksort, choosing one element as a pivot and partitioning the data in two based on the pivot, accordingly as less than or greater than the pivot. However, instead of recursing into both sides, as in quicksort, quickselect only recurses into one side – the side with the element it is searching for. This reduces the average complexity from to . As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the 'th element, it also partially sorts the data. See selection algorithm for further discussion of the connection with sorting. ==Algorithm== In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts, those less than a certain element, and those greater than or equal to the element. Here is pseudocode that performs a partition about the element list():function partition(list, left, right, pivotIndex) pivotValue := list() swap list() and list() ''// Move pivot to end'' storeIndex := left for i from left to right-1 if list() < pivotValue swap list() and list() increment storeIndex swap list() and list() ''// Move pivot to its final place'' return storeIndex In quicksort, we recursively sort both branches, leading to best-case Ω(''n'' log ''n'') time. However, when doing selection, we already know which partition our desired element lies in, since the pivot is in its final sorted position, with all those preceding it in an unsorted order and all those following it in an unsorted order. Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect: ''// Returns the n-th smallest element of list within left..right inclusive'' ''// (i.e. left <= n <= right).'' ''// The search space within the array is changing for each round - but the list'' ''// is still the same size.Thus, n does not need to be updated with each round.'' function select(list, left, right, n) if left = right ''// If the list contains only one element,'' return list() ''// return that element'' pivotIndex := ... ''// select a pivotIndex between left and right,'' ''// e.g.,'' left + floor(rand() * (right - left + 1)) pivotIndex := partition(list, left, right, pivotIndex) ''// The pivot is in its final sorted position'' if n = pivotIndex return list() else if n < pivotIndex return select(list, left, pivotIndex - 1, n) else return select(list, pivotIndex + 1, right, n) Note the resemblance to quicksort: just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only O(log ''n'') of its O(''n'') partitions. This simple procedure has expected linear performance, and, like quicksort, has quite good performance in practice. It is also an in-place algorithm, requiring only constant memory overhead, since the tail recursion can be eliminated with a loop like this: function select(list, left, right, n) loop if left = right return list() pivotIndex := ... ''// select pivotIndex between left and right'' pivotIndex := partition(list, left, right, pivotIndex) if n = pivotIndex return list() else if n < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「quickselect」の詳細全文を読む スポンサード リンク
|