Selection algorithm: Difference between revisions

Revision as of 02:05, 30 March 2023

Revision as of 04:32, 30 March 2023

Line 28:

*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}}

*The [[Floyd–Rivest algorithm]], 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 antwo elementelements nearsomewhat above and below position <math>rk/n</math> of the sample to use as the pivotpivots. ThisWith this choice, causesit the pivot to beis likely tothat be<math>k</math> closeis insandwiched the sorted sequence tobetween the eventualtwo result of the overall selection algorithmpivots, so that eachafter pivoting steponly eliminatesa assmall manynumber of data values asbetween possible.the Itpivots canare alsoleft befor describeda asrecursive selectingcall. twoThis pivots,method onecan achieve an expected tonumber beof abovecomparisons that is <math>n+\min(k,n-k)+o(n)</math>.{{r|floriv}} In their original work, Floyd and theRivest otherclaimed belowthat the <math>ko(n)</math>. Withterm acould carefulbe choicemade ofas samplesmall size,as with<math>O(\sqrt an)</math> carefulby choicea ofrecursive whichsampling pivot to compare against firstscheme, and withbut the samecorrectness methodof appliedtheir recursivelyanalysis tohas findbeen thequestioned.{{r|brown|prt}} pivotsInstead, thismore methodrigorous cananalysis achievehas anshown expectedthat numbera version of comparisonstheir thatalgorithm isachieves <math>n+\min(k,n-k)+O(\sqrt{n\log n})</math> for this term.{{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.

*Hybrid algorithms such as [[introselect]] can be used to achieve the practical performance of quickselect with a fallback to medians of medians guaranteeing worst-case <math>O(n)</math> time.{{r|musser}}

Line 82:

| volume = 7

| year = 1973}}</ref>

<ref name=brown>{{citation

| last = Brown | first = Theodore

| date = September 1976

| doi = 10.1145/355694.355704

| issue = 3

| journal = ACM Transactions on Mathematical Software

| pages = 301–304

| title = Remark on Algorithm 489

| volume = 2}}</ref>

<ref name=clrs>{{Introduction to Algorithms|edition=3|chapter=Chapter 9: Medians and order statistics|pages=213–227}}; "Section 14.1: Dynamic order statistics", pp. 339–345</ref>

Line 149 ⟶ 159:

| title = Introspective sorting and selection algorithms

| volume = 27}}</ref>

<ref name=prt>{{citation

| last1 = Postmus | first1 = J. T.

| last2 = Rinnooy Kan | first2 = A. H. G. | author2-link = Alexander Rinnooy Kan

| last3 = Timmer | first3 = G. T.

| doi = 10.1145/182.358440

| issue = 11

| journal = [[Communications of the ACM]]

| mr = 784120

| pages = 878–881

| title = An efficient dynamic selection method

| volume = 26

| year = 1983}}</ref>

<ref name=iso>Section 25.3.2 of ISO/IEC 14882:2003(E) and 14882:1998(E)</ref>