Content deleted Content added
→Pivoting: ce |
Kleinberg & Tardos |
||
Line 23:
===Pivoting===
Many methods for selection are based on choosing a special "pivot" element from the input, and using comparisons with this element to divide the remaining <math>n-1</math> input values into two subsets: the set <math>L</math> of elements less than the pivot, and the set <math>R</math> of elements greater than the pivot. The algorithm can then determine where the <math>k</math>th smallest value is to be found, based on a comparison of <math>k</math> with the sizes of these sets. In particular, if <math>k\le|L|</math>, the <math>k</math>th smallest value is in <math>L</math>, and can be found recursively by applying the same selection algorithm to <math>L</math>. If <math>k=|L|+1</math>, then the <math>k</math>th smallest value is the pivot, and it can be returned immediately. In the remaining case, the <math>k</math>th smallest value is in <math>R</math>, and more specifically it is the element in position <math>k-|L|-1</math> of <math>R</math>. It can be found by applying a selection algorithm recursively, seeking the value in this position in <math>R</math>.{{r|kletar}}
As with the related pivoting-based [[quicksort]] algorithm, the partition of the input into <math>L</math> and <math>R</math> may be done by making new collections for these sets, or by a method that partitions a given list or array data type in-place. Details vary depending on how the input collection is represented.<ref>For instance, Cormen et al. use an in-place array partition, while Kleinberg and Tardos describe the input as a set and use a method that partitions it into two new sets.</ref> The time to compare the pivot against all the other values is <math>O(n)</math>.{{r|kletar}} However, pivoting methods differ in how they choose the pivot, which affects how big the subproblems in each recursive call will be. The efficiency of these methods depends greatly on the choice of the pivot.
*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] to <math>O(n)</math>. However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each call.{{r|kletar}}▼
*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> and <math>R</math>, quickselect only makes one of these two calls. Its [[expected time]] is <math>O(n)</math>.{{r|clrs|kletar}}▼
▲*If the pivot were exactly at the median of the input, then each recursive call would have at most half as many values as the previous call, and the total times would add in a [[geometric series]] to <math>O(n)</math>. However, finding the median is itself a selection problem, on the entire original input. Trying to find it by a recursive call to a selection algorithm would lead to an infinite recursion, because the problem size would not decrease in each call.
▲*[[Quickselect]] chooses the pivot uniformly at random from the input values. It can be described as a variant of [[quicksort]], with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections <math>L</math> and <math>R</math>, quickselect only makes one of these two calls. Its [[expected time]] is <math>O(n)</math>.{{r|clrs}}
*A variation of quickselect chooses a pivot by randomly sampling a subset of <math>r</math> data values, for some sample size <math>r</math>, and then recursively selecting an element near position <math>rk/n</math> of the sample to use as the pivot. This choice causes the pivot to be likely to be close in the sorted sequence to the eventual result of the overall selection algorithm, so that each pivoting step eliminates as many values as possible. With a careful choice of sample size, and with the index of the recursive selection call chosen either somewhat above or somewhat below <math>rk/n</math> (to control which side of <math>k</math> the pivot is likely to land on), this method can achieve an expected number of comparisons that is <math>n+\min(k,n-k)+O(\sqrt n)</math>.{{r|floriv}}
*The [[median of medians]] method partitions the input into sets of five elements, and then uses some other method (rather than a recursive call) to find the median of each of these sets in constant time per set. It then recursively calls the same selection algorithm to find the median of these <math>n/5</math> medians, using the result as its pivot. It can be shown that, for this choice of pivot, <math>\max(|L|,|R|)\le 7n/10</math>. Thus, a problem on <math>n</math> elements is reduced to two recursive problems on <math>n/5</math> and at most <math>7n/10</math> elements. The total size of these two recursive subproblems is at most <math>9n/10</math>, allowing the total time to be analyzed as a geometric series adding to <math>O(n)</math>. Unlike quickselect, this algorithm is deterministic, not randomized.{{r|clrs|bfprt}} It was the first linear-time deterministic selection algorithm known,{{r|bfprt}} and is commonly taught in undergraduate algorithms classes as an example of a [[divide and conquer]] algorithm that does not divide into two equal subproblems. However, the high constant factors in its <math>O(n)</math> time bound make it unsuitable for practical use.
Line 119 ⟶ 117:
| title = Algorithm 65: Find
| volume = 4}}</ref>
<ref name=kletar>{{cite book
| last1 = Kleinberg | first1 = Jon | author1-link = Jon Kleinberg
| last2 = Tardos | first2 = Éva | author2-link = Éva Tardos
| contribution = 13.5 Randomized divide and conquer: median-finding and quicksort
| isbn = 9780321295354
| pages = 727–734
| publisher = Addison-Wesley
| title = Algorithm Design
| year = 2006}}</ref>
<ref name=kpaths>{{cite journal
| |||