2661:
sequence of two-element totally ordered sets. The elements used as the inputs to this factory could either be input values that have not been compared with anything yet, or "waste" values produced by other factories. The goal of a factory-based algorithm is to combine together different factories, with the outputs of some factories going to the inputs of others, in order to eventually obtain a partial order in which one element (the
4710:
2145:
3465:
This same method can be applied more generally to data organized as any kind of heap-ordered tree (a tree in which each node stores one value in which the parent of each non-root node has a smaller value than its child). This method of performing selection in a heap has been applied to problems of
809:
algorithms may be used, these are generally slower than the linear time that may be achieved using specialized selection algorithms. Nevertheless, the simplicity of this approach makes it attractive, especially when a highly-optimized sorting routine is provided as part of a runtime library, but a
3876:
running time of the selection algorithms described above is necessary, because a selection algorithm that can handle inputs in an arbitrary order must take that much time to look at all of its inputs. If any one of its input values is not compared, that one value could be the one that should have
2152:
method. Each set of five elements is shown as a column of dots in the figure, sorted in increasing order from top to bottom. If their medians (the green and purple dots in the middle row) are sorted in increasing order from left to right, and the median of medians is chosen as the pivot, then the
4249:
the same number that would be obtained by holding a single-elimination tournament with a run-off tournament among the values that lost to the smallest value. However, the expected number of comparisons of a randomized selection algorithm can be better than this bound; for instance, selecting the
2660:
of certain specified types, on small subsets of input values, by using comparisons to combine smaller partial orders. As a very simple example, one type of factory can take as input a sequence of single-element partial orders, compare pairs of elements from these orders, and produce as output a
1609:
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 is chosen badly, the running time of this method can be as slow
5276:
for reverse sorted data. In average cases, there are likely to be few heap updates and most input elements are processed with only a single comparison. For example, extracting the 100 largest or smallest values out of 10,000,000 random inputs makes 10,009,401 comparisons on average.
4717:
of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the
3877:
been selected, and the algorithm can be made to produce an incorrect answer. Beyond this simple argument, there has been a significant amount of research on the exact number of comparisons needed for selection, both in the randomized and deterministic cases.
311:
or that some consistent tie-breaking method has been used to assign an ordering to pairs of items with the same value as each other. Another variation in the problem definition concerns the numbering of the ordered values: is the smallest value obtained by
5060:, related to heapselect, that finds the smallest value using a single-elimination tournament and then repeatedly uses a smaller tournament among the values eliminated by the eventual tournament winners to find the next successive values until reaching the
5161:
elements in the collection. Then, each subsequent item of the collection may replace the largest or smallest element in the heap if it is smaller or larger than this element. The algorithm's memory usage is superior to heapselect (the former only holds
3952:
values that are not selected must each have been determined to be non-minimal, by being the largest in some comparison, and no two of these values can be largest in the same comparison. The same argument applies symmetrically to selecting the
1689:
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
376:
following the usual
English-language conventions for the smallest, second-smallest, etc.? This article follows the conventions used by Cormen et al., according to which all values are distinct and the minimum value is obtained from
2224:
method partitions the input into sets of five elements, and uses some other non-recursive method to find the median of each of these sets in constant time per set. It then recursively calls itself to find the median of these
4615:
5054:
1954:
is sandwiched between the two pivots, so that after pivoting only a small number of data values between the pivots are left for a recursive call. This method can achieve an expected number of comparisons that is
4508:
3357:
3171:
4245:
4698:
3052:, it may be possible to perform selection in an amount of time that is sublinear in the number of values. As a simple case of this, for data already sorted into an array, selecting the
2324:
1572:
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
5091:
Very few languages have built-in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the
3600:
2840:
2126:
3959:
The next simplest case is selecting the second-smallest. After several incorrect attempts, the first tight lower bound on this case was published in 1964 by Soviet mathematician
4359:
2016:
7185:
4659:
5236:
1653:
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
796:
6446:
3837:
2885:
2080:
6608:
Chaudhuri, Shiva; Hagerup, Torben; Raman, Rajeev (1993). "Approximate and exact deterministic parallel selection". In
Borzyszkowski, Andrzej M.; Sokolowski, Stefan (eds.).
3789:
810:
selection algorithm is not. For inputs of moderate size, sorting can be faster than non-random selection algorithms, because of the smaller constant factors in its running
950:
5762:
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.
5368:) who in 1883 pointed out that the usual design of single-elimination sports tournaments does not guarantee that the second-best player wins second place, and to work of
2975:
5274:
4190:
3635:
3456:
1034:
3716:
Going beyond the comparison model of computation, faster times per operation are possible for values that are small integers, on which binary arithmetic operations are
3710:
3545:
3105:
2932:
1247:
532:
1646:
5372:
circa 1930, who followed up this same line of thought by asking for a tournament design that can make this guarantee, with a minimum number of games played (that is,
1477:
1363:
657:
3037:
3009:
2757:
4111:
3244:
2801:
introduced the parallel comparison tree model for analyzing these algorithms, and proved that in this model selection using a linear number of comparisons requires
2438:
2405:
2213:
2182:
1092:
612:
4388:
3874:
3768:
can be used to solve selection queries approximately, by finding a value whose position in the ordering of the elements (if it were added to them) would be within
3396:
2561:
2518:
2471:
2047:
1932:
1782:
1685:
1605:
814:
This method also produces a sorted version of the collection, which may be useful for other later computations, and in particular for selection with other choices
194:
155:
7340:
6767:
4812:
4513:
4079:
4053:
4027:
3950:
3924:
2734:
2708:
2374:
2251:
1126:
454:
402:
372:
338:
7108:
1827:
7314:
7292:
7247:
6872:
5980:
5958:
5310:
5180:
5159:
5139:
5079:
4922:
4899:
4876:
4853:
4832:
4784:
4763:
4743:
4427:
4297:
4275:
4155:
4135:
4001:
3981:
3898:
3809:
3762:
3742:
3673:
3508:
3418:
3265:
3217:
3193:
3071:
2779:
2680:
2633:
2612:
2592:
2346:
1952:
1899:
1877:
1849:
1804:
1746:
1725:
1570:
1550:
1522:
1498:
1433:
1409:
1386:
1318:
1294:
1270:
1209:
1187:
1166:
1146:
1056:
994:
972:
902:
863:
834:
752:
729:
692:
574:
554:
476:
426:
270:
248:
225:
122:
77:
56:
5182:
elements in memory at a time while the latter requires manipulating the entire dataset into memory). Running time depends on data ordering. The best case is
3963:. It can be shown by observing that selecting the second-smallest also requires distinguishing the smallest value from the rest, and by considering the number
4964:
1102:
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
4137:(subject to consistency with at least one possible ordering) rather than by the numerical values of the given items, shows that it is possible to force
6610:
Mathematical
Foundations of Computer Science 1993, 18th International Symposium, MFCS'93, Gdansk, Poland, August 30 – September 3, 1993, Proceedings
4250:
second-smallest of six elements requires seven comparisons in the worst case, but may be done by a randomized algorithm with an expected number of
5312:
values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running
3654:
structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the
871:, in which the teams who lost to the eventual winner play another mini-tournament to determine second place, can be seen as an instance of this
288:
with a numeric key. However, they are not assumed to have been already sorted. Often, selection algorithms are restricted to a comparison-based
4713:
Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a
6234:
2891:
In a randomized parallel comparison tree model it is possible to perform selection in a bounded number of steps and a linear number of
4434:
7251:
largest using binary errorless comparisons (Report). School of
Statistics Technical Reports. Vol. 121. University of Minnesota.
6954:
3273:
4390:
term. The argument is made directly for deterministic algorithms, with a number of comparisons that is averaged over all possible
4029:
of these values must be found larger than another value in a second comparison in order to rule them out as second-smallest. With
6450:
6261:
5651:
5693:
Space-Efficient Data
Structures, Streams, and Algorithms – Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday
2215:
elements in the lower right quadrant will be greater than the pivot, showing that many elements will be eliminated by pivoting.
2534:
can be used to achieve the practical performance of quickselect with a fallback to medians of medians guaranteeing worst-case
7001:
6984:
6635:
5795:
5708:
5554:
161:. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted
5691:(2013). "A survey on priority queues". In Brodnik, Andrej; López-Ortiz, Alejandro; Raman, Venkatesh; Viola, Alfredo (eds.).
5117:
functions for returning the smallest or largest elements from a collection, in sorted order. The implementation maintains a
7189:
7489:
7129:
6400:
6115:
5747:
5510:
3651:
2736:
others. A careful design of these factories leads to an algorithm that, when applied to median-finding, uses at most
7395:
6959:
55th IEEE Annual
Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014
3113:
2140:
seeded with only logarithmically many true random bits has been proven to run in linear time with high probability.
6651:
Dietz, Paul F.; Raman, Rajeev (1999). "Small-rank selection in parallel, with applications to heap construction".
4199:
7112:
Proceedings of the 17th Annual ACM Symposium on Theory of
Computing, May 6–8, 1985, Providence, Rhode Island, USA
6105:
4667:
1707:, with the same pivoting strategy, but where quicksort makes two recursive calls to sort the two subcollections
7044:
6565:
5415:
3474:
7470:
Lawn Tennis
Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method
6911:
Babenko, Maxim; Kolesnichenko, Ignat; Smirnov, Ivan (2019). "Cascade heap: towards time-optimal extractions".
7511:
5106:
4361:
comparisons, in the average case, matching the number of comparisons of the Floyd–Rivest algorithm up to its
2257:
2137:
868:
20:
58:
th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the
6491:
2484:
2133:
3551:
2899:
model of computing, with exclusive read exclusive write memory access, selection can be performed in time
2804:
2089:
6814:
4302:
1959:
7155:
5500:
4629:
1856:
277:
5185:
763:
307:
To simplify the problem, some works on this problem assume that the values are all distinct from each
7438:
6876:
6697:
6528:
6361:
6313:
6045:
5911:
5364:. They trace the formulation of the selection problem to work of Charles L. Dodgson (better known as
5092:
4402:, it also applies to the expected number of comparisons for a randomized algorithm on its worst-case
2574:
The deterministic selection algorithms with the smallest known numbers of comparisons, for values of
285:
6410:
3814:
2849:
2132:
Although the usual analysis of both quickselect and the Floyd–Rivest algorithm assumes the use of a
2052:
6957:; Thorup, Mikkel (2014). "Dynamic integer sets with optimal rank, select, and predecessor search".
4624:
The special case of median-finding has a slightly larger lower bound on the number of comparisons,
3771:
5688:
3983:
of comparisons involving the smallest value that an algorithm for this problem makes. Each of the
1502:
It can be found by applying a selection algorithm recursively, seeking the value in this position
911:
300:
that can determine the relative ordering of any two values, but may not perform any other kind of
4765:
for which the exact number of comparisons needed by an optimal selection algorithm is known. The
4619:
3467:
2937:
5241:
4162:
3607:
3423:
1001:
5384:
3680:
3515:
3084:
2902:
1216:
491:
162:
7477:
6777:. OASIcs. Vol. 69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 5:1–5:21.
4961:
Most, but not all, of the entries on the left half of each row can be found using the formula
4903:
smallest requires exactly the same number of comparisons, in the worst case, as selecting the
1615:
6653:
6036:
3485:
In the other direction, linear time selection algorithms have been used as a subroutine in a
1440:
1326:
622:
281:
3016:
2988:
2739:
2407:
elements (after the pivot is used). The total size of these two recursive subproblems is at
1390:
smallest value is the pivot, and it can be returned immediately. In the remaining case, the
7379:
7210:
7065:
7025:
6932:
6897:
6837:
6775:
2nd
Symposium on Simplicity in Algorithms, SOSA 2019, January 8–9, 2019, San Diego, CA, USA
6770:
6718:
6674:
6586:
6549:
6512:
6471:
6382:
6334:
6282:
6195:
6164:
6068:
5873:
5839:
5674:
5564:
5488:
5447:
4084:
3765:
3721:
3647:
3222:
2412:
2379:
2187:
2156:
1063:
583:
343:
289:
6626:
4958:
9 12 14 15 16 16 15 14 12 9
4364:
3850:
3372:
2537:
2494:
2447:
2023:
1906:
1758:
1661:
1581:
170:
131:
8:
7319:
6746:
6526:
Reischuk, Rüdiger (1985). "Probabilistic parallel algorithms for sorting and selection".
5779:
4791:
4058:
4032:
4006:
3929:
3903:
2713:
2687:
2351:
2228:
1105:
433:
381:
351:
317:
297:
7090:
6248:
6199:
5083:
smallest. Some of the larger entries were proven to be optimal using a computer search.
4880:
smallest value from an input of that size. The rows are symmetric because selecting the
2642:
1809:
844:, the scan can be done in tandem with the sort, and the sort can be terminated once the
7361:
7299:
7277:
7232:
7069:
6962:
6936:
6857:
6778:
6590:
6338:
6286:
6168:
6141:
6132:
6072:
6017:
5965:
5943:
5930:
5877:
5568:
5451:
5424:
5295:
5165:
5144:
5124:
5064:
4907:
4884:
4861:
4838:
4817:
4769:
4748:
4728:
4412:
4399:
4282:
4260:
4140:
4120:
4003:
items that were compared to the smallest value is a candidate for second-smallest, and
3986:
3966:
3883:
3794:
3747:
3727:
3658:
3639:
3493:
3466:
listing multiple solutions to combinatorial optimization problems, such as finding the
3403:
3250:
3202:
3178:
3056:
2794:
2764:
2665:
2618:
2597:
2577:
2331:
1937:
1884:
1862:
1834:
1789:
1731:
1710:
1555:
1535:
1507:
1483:
1418:
1394:
1371:
1303:
1279:
1255:
1194:
1172:
1151:
1131:
1041:
979:
957:
887:
848:
819:
737:
714:
677:
559:
539:
461:
411:
255:
233:
210:
107:
62:
41:
7408:
7004:(2005). "An improved data stream summary: the count-min sketch and its applications".
6404:
6274:
5665:
5643:
2253:
medians. Using the resulting median of medians as the pivot produces a partition with
1699:
chooses the pivot uniformly at random from the input values. It can be described as a
696:
smallest value in a collection of values can be performed by the following two steps:
7485:
7125:
6980:
6940:
6692:
6631:
6504:
6463:
6111:
5831:
5791:
5743:
5704:
5596:
5550:
5506:
5341:
4194:
Therefore, the worst-case number of comparisons needed to select the second smallest
3460:
2221:
2149:
2086:
Instead, more rigorous analysis has shown that a version of their algorithm achieves
707:
101:
7073:
6290:
6172:
6021:
5572:
5455:
205:
An algorithm for the selection problem takes as input a collection of values, and a
7447:
7365:
7353:
7252:
7198:
7115:
7053:
7013:
6972:
6920:
6885:
6823:
6788:
6706:
6662:
6621:
6613:
6594:
6574:
6537:
6500:
6459:
6370:
6342:
6322:
6270:
6230:
6203:
6150:
6076:
6054:
6009:
5983:
5934:
5920:
5861:
5827:
5812:
5783:
5696:
5660:
5542:
5484:
5433:
4081:
values being the larger in at least two comparisons, there are a total of at least
3960:
1700:
1654:
556:
is even, there are two choices for the median, obtained by rounding this choice of
252:
smallest of these values, or, in some versions of the problem, a collection of the
27:
6221:
Musser, David R. (August 1997). "Introspective sorting and selection algorithms".
5881:
7344:
7270:
7206:
7061:
7039:
7021:
7017:
6928:
6893:
6833:
6714:
6670:
6582:
6545:
6508:
6467:
6378:
6330:
6278:
6160:
6064:
5898:
5869:
5835:
5700:
5695:. Lecture Notes in Computer Science. Vol. 8066. Springer. pp. 150–163.
5670:
5627:
5560:
5443:
5349:
5056:
This describes the number of comparisons made by a method of Abdollah Hadian and
4114:
3646:
For a collection of data values undergoing dynamic insertions and deletions, the
806:
800:
293:
81:
6612:. Lecture Notes in Computer Science. Vol. 711. Springer. pp. 352–361.
6396:
4955:
8 11 12 14 14 14 12 11 8
4952:
7 9 11 12 12 11 9 7
6851:
6793:
6486:
6356:
6256:
5496:
5369:
3486:
3478:
3049:
2798:
2651:
2082:
by a recursive sampling scheme, but the correctness of their analysis has been
1859:, a variation of quickselect, chooses a pivot by randomly sampling a subset of
1168:
of elements greater than the pivot. The algorithm can then determine where the
841:
158:
7202:
6924:
6889:
6326:
5865:
5546:
2483:
and is commonly taught in undergraduate algorithms classes as an example of a
1903:
and then recursively selecting two elements somewhat above and below position
7505:
7465:
6617:
6252:
5731:
5639:
5631:
5534:
5390:
5365:
5361:
5353:
4714:
2657:
2646:
1751:
276:
the values into an order from smallest to largest; for instance, they may be
7057:
6578:
5738:(2006). "13.5 Randomized divide and conquer: median-finding and quicksort".
5735:
4946:
5 7 8 8 7 5
4857:
number within each row gives the number of comparisons needed to select the
4610:{\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}
2981:
With concurrent memory access, slightly faster parallel time is possible in
7225:
6828:
6809:
6666:
6101:
5335:
5057:
4722:
2896:
7451:
7357:
6235:
10.1002/(sici)1097-024x(199708)27:8<983::aid-spe117>3.0.co;2-#
6155:
6136:
6013:
5987:
5925:
5906:
5541:. Texts in Computer Science (Third ed.). Springer. pp. 514–516.
3489:
data structure related to the heap, improving the time for extracting its
867:
element has been found. One possible design of a consolation bracket in a
760:
The time for this method is dominated by the sorting step, which requires
6976:
5623:
5345:
5323:
5118:
4391:
4117:, in which the outcome of each comparison is chosen in order to maximize
3364:
2531:
2184:
elements in the upper left quadrant will be less than the pivot, and the
1696:
125:
97:
7256:
7120:
5438:
5419:
5049:{\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}
7433:
6059:
6040:
5902:
5635:
5492:
5357:
5327:
880:
479:
301:
272:
smallest values. For this to be well-defined, it should be possible to
6207:
4949:
6 8 10 10 10 8 6
3481:
heap-ordered tree, and then applying this selection algorithm to this
1298:
and can be found recursively by applying the same selection algorithm
7149:
7145:
6740:
6308:
6304:
5846:
5340:
The first known linear time deterministic selection algorithm is the
1704:
1529:
35:
7087:
Bent, Samuel W.; John, John W. (1985). "Finding the median requires
6710:
6541:
6374:
2442:
allowing the total time to be analyzed as a geometric series adding
1934:
of the sample to use as pivots. With this choice, it is likely that
6783:
4408:
For deterministic algorithms, it has been shown that selecting the
876:
840:
For a sorting algorithm that generates one item at a time, such as
7042:(2010). "Comparison-based time-space lower bounds for selection".
6967:
5813:"Exponential bounds for the running time of a selection algorithm"
84:. Selection includes as special cases the problems of finding the
3109:
with sorted rows and columns, selection may be performed in time
700:
408:
With these conventions, the maximum value, among a collection of
273:
93:
85:
6186:
Gurwitz, Chaya (1992). "On teaching median-finding algorithms".
6107:
The Art of Computer Programming, Volume 3: Sorting and Searching
4725:
supplies the following triangle of numbers summarizing pairs of
4503:{\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}
5281:
4814:
in the top row) gives the numbers of comparisons for inputs of
3075:
element may be performed by a single array lookup, in constant
2977:
processors, which is optimal both in time and in the number of
2479:
It was the first linear-time deterministic selection algorithm
483:
89:
6695:(1984). "Generalized selection and ranking: sorted matrices".
5939:
See also "Algorithm 489: the algorithm SELECT—for finding the
5393:, application of median-finding algorithms in image processing
5387:, algorithms for higher-dimensional generalizations of medians
4709:
3352:{\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}
6000:
Brown, Theodore (September 1976). "Remark on Algorithm 489".
5505:(3rd ed.). MIT Press and McGraw-Hill. pp. 213–227.
5096:
4943:
4 6 6 6 4
3764:
to solve selection queries exactly for dynamic data, but the
2846:
Researchers later found parallel algorithms for selection in
2144:
7482:
The Mathematical World of Charles L. Dodgson (Lewis Carroll)
6910:
6395:
3811:, for a sketch whose size is within logarithmic factors of
1576:
The time to compare the pivot against all the other values
19:
For simulated natural selection in genetic algorithms, see
6247:
5595:
Erickson, Jeff (June 2019). "1.8: Linear-time selection".
5483:
2020:
In their original work, Floyd and Rivest claimed that the
7114:. Association for Computing Machinery. pp. 213–216.
2475:
Unlike quickselect, this algorithm is deterministic, not
1806:, the probability that its number of comparisons exceeds
733:
element; otherwise, scan the sorted sequence to find the
7273:; Kelly, Wayne; Pugh, William (July 1996). "Finding the
6743:(2019). "Selection from heaps, row-sorted matrices, and
6034:
4055:
values being the larger in at least one comparison, and
1191:
smallest value is to be found, based on a comparison of
96:
element in the collection. Selection algorithms include
6104:(1998). "Section 5.3.3: Minimum-comparison selection".
5517:; "Section 14.1: Dynamic order statistics", pp. 339–345
3276:
7396:
comparison of algorithm performance on best-case data
7322:
7302:
7280:
7235:
7158:
7093:
6860:
6749:
6738:
6607:
6413:
5968:
5946:
5298:
5244:
5188:
5168:
5147:
5127:
5067:
4967:
4910:
4887:
4864:
4841:
4820:
4794:
4772:
4751:
4731:
4670:
4632:
4516:
4437:
4415:
4367:
4305:
4285:
4263:
4202:
4165:
4143:
4123:
4087:
4061:
4035:
4009:
3989:
3969:
3932:
3906:
3886:
3853:
3817:
3797:
3774:
3750:
3730:
3683:
3661:
3610:
3554:
3518:
3496:
3426:
3406:
3375:
3253:
3225:
3205:
3181:
3116:
3087:
3079:
For values organized into a two-dimensional array of
3059:
3019:
2991:
2940:
2905:
2852:
2807:
2767:
2742:
2716:
2690:
2668:
2621:
2600:
2580:
2540:
2497:
2450:
2415:
2382:
2354:
2334:
2260:
2231:
2190:
2159:
2092:
2055:
2026:
1962:
1940:
1909:
1887:
1865:
1837:
1812:
1792:
1761:
1734:
1713:
1664:
1618:
1584:
1558:
1538:
1510:
1486:
1443:
1421:
1397:
1374:
1329:
1306:
1282:
1258:
1219:
1197:
1175:
1154:
1134:
1108:
1066:
1044:
1004:
982:
960:
914:
890:
851:
822:
766:
740:
717:
680:
625:
586:
562:
542:
494:
464:
436:
414:
384:
354:
320:
258:
236:
213:
173:
134:
110:
65:
44:
6999:
5622:
5499:(2009) . "Chapter 9: Medians and order statistics".
2524:
and slower even than sorting for inputs of moderate
1437:
and more specifically it is the element in position
6690:
6407:(1989). "Optimal parallel selection has complexity
1750:quickselect only makes one of these two calls. Its
7334:
7308:
7286:
7241:
7179:
7102:
6866:
6810:"An optimal algorithm for selection in a min-heap"
6761:
6440:
6110:(2nd ed.). Addison-Wesley. pp. 207–219.
5974:
5952:
5304:
5268:
5230:
5174:
5153:
5133:
5073:
5048:
4916:
4893:
4870:
4847:
4826:
4806:
4778:
4757:
4737:
4692:
4653:
4609:
4502:
4421:
4382:
4353:
4291:
4269:
4239:
4184:
4149:
4129:
4105:
4073:
4047:
4021:
3995:
3975:
3944:
3918:
3892:
3868:
3831:
3803:
3783:
3756:
3736:
3704:
3677:element in the current set to all be performed in
3667:
3629:
3594:
3539:
3502:
3450:
3412:
3390:
3351:
3259:
3238:
3211:
3187:
3165:
3099:
3065:
3031:
3003:
2969:
2926:
2879:
2842:parallel steps, even for selecting the minimum or
2834:
2773:
2751:
2728:
2702:
2674:
2627:
2606:
2586:
2555:
2512:
2465:
2432:
2399:
2368:
2340:
2318:
2245:
2207:
2176:
2136:, a version of the Floyd–Rivest algorithm using a
2120:
2074:
2041:
2010:
1946:
1926:
1893:
1871:
1843:
1821:
1798:
1776:
1740:
1719:
1679:
1640:
1599:
1564:
1544:
1516:
1492:
1471:
1427:
1403:
1380:
1357:
1312:
1288:
1264:
1241:
1203:
1181:
1160:
1140:
1120:
1086:
1050:
1028:
988:
966:
944:
896:
857:
828:
790:
746:
723:
686:
651:
606:
568:
548:
526:
470:
448:
420:
396:
366:
332:
264:
242:
219:
188:
149:
116:
71:
50:
6563:Han, Yijie (2007). "Optimal parallel selection".
5333:and first analyzed in a 1971 technical report by
5103:method with a guarantee of expected linear time.
2797:for selection have been studied since 1975, when
2348:elements is reduced to two recursive problems on
7503:
7476:Wilson, Robin; Moktefi, Amirouche, eds. (2019).
7269:
6137:"Randomized algorithms and pseudorandom numbers"
5847:"On the probabilistic worst-case time of 'find'"
5778:
4312:
2261:
1969:
296:algorithms, where the algorithm has access to a
6130:
5730:
4704:
6953:
6359:(1975). "Parallelism in comparison problems".
5292:functions, which return the maximal (minimal)
4940:3 4 4 3
3166:{\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}
2520:time bound make it slower than quickselect in
7475:
6484:
5038:
4997:
4473:
4440:
3344:
3282:
3158:
3122:
1211:with the sizes of these sets. In particular,
1148:of elements less than the pivot, and the set
706:If the output of the sorting algorithm is an
6807:
6801:
5238:for already sorted data. The worst-case is
4240:{\displaystyle n+\lceil \log _{2}n\rceil -2}
4228:
4209:
3043:
7223:
6961:. IEEE Computer Society. pp. 166–175.
5897:
4693:{\displaystyle \varepsilon \approx 2^{-80}}
1532:algorithm, the partition of the input into
104:algorithm. When applied to a collection of
7110:comparisons". In Sedgewick, Robert (ed.).
6769:using soft heaps". In Fineman, Jeremy T.;
6650:
5590:
5588:
5586:
5584:
5582:
5413:
2491:However, the high constant factors in its
673:As a baseline algorithm, selection of the
7409:"mink: Find k smallest elements of array"
7119:
6966:
6827:
6792:
6782:
6686:
6684:
6625:
6154:
6058:
6002:ACM Transactions on Mathematical Software
5924:
5893:
5891:
5664:
5437:
3246:items less than the selected item in the
2376:elements (to find the pivot) and at most
2148:Visualization of pivot selection for the
668:
7484:. Oxford University Press. p. 129.
7144:
7086:
6850:
6739:Kaplan, Haim; Kozma, László; Zamir, Or;
6525:
6519:
6303:
6096:
6094:
6092:
6090:
6088:
6086:
5774:
5772:
5770:
5768:
5726:
5724:
5722:
5720:
5594:
5529:
5527:
5525:
5523:
5409:
5407:
4708:
2710:other elements and smaller than another
2143:
7464:
7458:
6734:
6732:
6730:
6728:
6451:Journal of Computer and System Sciences
6355:
6349:
6262:Journal of Computer and System Sciences
6185:
6179:
6041:"An efficient dynamic selection method"
5844:
5820:Journal of Computer and System Sciences
5810:
5804:
5652:Journal of Computer and System Sciences
5618:
5616:
5614:
5612:
5610:
5608:
5579:
5141:elements, and initialized to the first
3458:time bound that would be obtained from
3011:term in the time bound can be replaced
2319:{\displaystyle \max(|L|,|R|)\leq 7n/10}
1128:input values into two subsets: the set
7504:
7401:
7372:
7217:
7080:
6993:
6947:
6844:
6681:
6644:
6478:
6220:
6214:
6124:
5888:
5687:
5537:(2020). "17.3: Median and selection".
5533:
5479:
5477:
5475:
5473:
5471:
5469:
5467:
5465:
3048:When data is already organized into a
2789:
7432:
7426:
6100:
6083:
5999:
5993:
5765:
5717:
5681:
5520:
5404:
16:Method for finding kth smallest value
7190:SIAM Journal on Discrete Mathematics
7138:
7038:
7032:
6725:
6389:
6297:
5907:"Expected time bounds for selection"
5742:. Addison-Wesley. pp. 727–734.
5605:
3595:{\displaystyle O(\log ^{*}n+\log k)}
3219:one-dimensional sorted arrays, with
2835:{\displaystyle \Omega (\log \log n)}
2487:that does not divide into two equal
2121:{\displaystyle O({\sqrt {n\log n}})}
200:
7436:(July 1961). "Algorithm 65: Find".
7263:
7152:(2001). "Median selection requires
6904:
6601:
6562:
6556:
6241:
6028:
5462:
5385:Geometric median § Computation
5086:
4788:row of the triangle (starting with
3473:in a weighted graph, by defining a
1528:As with the related pivoting-based
13:
5326:was presented without analysis by
4484:
4354:{\displaystyle n+\min(k,n-k)-O(1)}
2808:
2011:{\displaystyle n+\min(k,n-k)+o(n)}
767:
14:
7523:
7180:{\displaystyle (2+\varepsilon )N}
6223:Software: Practice and Experience
5788:Algorithm Design and Applications
4654:{\displaystyle (2+\varepsilon )n}
3652:self-balancing binary search tree
3420:of the heap, and faster than the
486:of the collection is obtained by
6311:(1999). "Selecting the median".
5231:{\displaystyle O((n-k)+k\log k)}
3400:This is independent of the size
883:algorithm, which can select the
791:{\displaystyle \Theta (n\log n)}
346:of arrays, or is it obtained by
4937:2 3 2
3842:
3477:of solutions in the form of an
3195:is small relative to the array
2049:term could be made as small as
7171:
7159:
7045:ACM Transactions on Algorithms
6808:Frederickson, Greg N. (1993).
6627:11858/00-001M-0000-0014-B748-C
6566:ACM Transactions on Algorithms
6489:(1990). "Parallel selection".
6441:{\displaystyle O(\log \log n)}
6435:
6417:
6259:(1976). "Finding the median".
6188:IEEE Transactions on Education
5756:
5263:
5248:
5225:
5207:
5195:
5192:
5033:
5015:
4992:
4980:
4645:
4633:
4573:
4561:
4526:
4520:
4497:
4487:
4468:
4454:
4377:
4371:
4348:
4342:
4333:
4315:
4256:More generally, selecting the
3863:
3857:
3832:{\displaystyle 1/\varepsilon }
3724:with memory sublinear in both
3699:
3687:
3589:
3558:
3534:
3522:
3445:
3430:
3385:
3379:
3339:
3320:
3153:
3136:
2964:
2944:
2921:
2909:
2880:{\displaystyle O(\log \log n)}
2874:
2856:
2829:
2811:
2759:comparisons. For other values
2684:smallest) is larger than some
2550:
2544:
2507:
2501:
2460:
2454:
2296:
2292:
2284:
2276:
2268:
2264:
2115:
2096:
2075:{\displaystyle O({\sqrt {n}})}
2069:
2059:
2036:
2030:
2005:
1999:
1990:
1972:
1771:
1765:
1674:
1668:
1635:
1622:
1594:
1588:
1459:
1451:
1345:
1337:
1235:
1227:
1023:
1008:
939:
918:
875:Applying this optimization to
785:
770:
576:down or up, respectively: the
513:
501:
183:
177:
144:
138:
124:values, these algorithms take
1:
6275:10.1016/S0022-0000(76)80029-3
5666:10.1016/S0022-0000(73)80033-9
5397:
5344:method, published in 1973 by
5109:'s standard library includes
5099:, which provides a templated
3784:{\displaystyle \varepsilon n}
2783:the number of comparisons is
2656:These are methods that build
2138:pseudorandom number generator
1879:data values, for some sample
869:single-elimination tournament
663:
21:Selection (genetic algorithm)
7018:10.1016/j.jalgor.2003.12.001
6505:10.1016/0166-218X(90)90128-Y
6492:Discrete Applied Mathematics
6464:10.1016/0022-0000(89)90035-4
5832:10.1016/0022-0000(84)90009-6
5701:10.1007/978-3-642-40273-9_11
4705:Exact numbers of comparisons
2637:are based on the concept of
2569:
2134:true random number generator
1829:is superexponentially small
945:{\displaystyle O(n+k\log n)}
7:
7472:. London: Macmillan and Co.
7413:Matlab R2023a documentation
7380:"heapq package source code"
6913:Theory of Computing Systems
6815:Information and Computation
5790:. Wiley. pp. 270–275.
5644:"Time bounds for selection"
5539:The Algorithm Design Manual
5378:
2970:{\displaystyle O(n/\log n)}
1097:
10:
7528:
7228:(May 1969). Selecting the
6794:10.4230/OASIcs.SOSA.2019.5
5786:(2015). "9.2: Selection".
5502:Introduction to Algorithms
5318:
5269:{\displaystyle O(n\log k)}
4185:{\displaystyle \log _{2}n}
3630:{\displaystyle \log ^{*}n}
3451:{\displaystyle O(k\log n)}
2530:Hybrid algorithms such as
1029:{\displaystyle O(n\log n)}
18:
7478:"Lawn tennis tournaments"
7439:Communications of the ACM
7203:10.1137/S0895480199353895
6925:10.1007/s00224-018-9866-1
6890:10.1137/S0097539795290477
6877:SIAM Journal on Computing
6698:SIAM Journal on Computing
6529:SIAM Journal on Computing
6362:SIAM Journal on Computing
6327:10.1137/S0097539795288611
6314:SIAM Journal on Computing
6046:Communications of the ACM
5912:Communications of the ACM
5866:10.1007/s00453-001-0046-2
5547:10.1007/978-3-030-54256-6
5093:Standard Template Library
3926:comparisons, because the
3880:Selecting the minimum of
3720:It is not possible for a
3705:{\displaystyle O(\log n)}
3540:{\displaystyle O(\log n)}
3363:Selection from data in a
3100:{\displaystyle m\times n}
3044:Sublinear data structures
2927:{\displaystyle O(\log n)}
1242:{\displaystyle k\leq |L|}
1094:used for median finding.
527:{\displaystyle k=(n+1)/2}
6618:10.1007/3-540-57182-5_27
6039:; Timmer, G. T. (1983).
5420:"Average case selection"
2641:, introduced in 1976 by
1703:algorithm, a variant of
1641:{\displaystyle O(n^{2})}
284:, or some other kind of
7058:10.1145/1721837.1721842
6691:Frederickson, Greg N.;
6579:10.1145/1290672.1290675
4620:binary entropy function
1472:{\displaystyle k-|L|-1}
1358:{\displaystyle k=|L|+1}
652:{\displaystyle k=n/2+1}
428:values, is obtained by
7394:; see also the linked
7336:
7310:
7288:
7243:
7181:
7104:
6868:
6829:10.1006/inco.1993.1030
6763:
6667:10.1006/jagm.1998.0971
6442:
5976:
5954:
5689:Brodal, Gerth Stølting
5306:
5270:
5232:
5176:
5155:
5135:
5075:
5050:
4918:
4895:
4872:
4849:
4828:
4808:
4780:
4759:
4739:
4719:
4694:
4655:
4611:
4504:
4423:
4384:
4355:
4293:
4271:
4241:
4186:
4151:
4131:
4107:
4075:
4049:
4023:
3997:
3977:
3946:
3920:
3894:
3870:
3833:
3805:
3785:
3758:
3738:
3706:
3669:
3631:
3596:
3541:
3504:
3452:
3414:
3392:
3353:
3313:
3261:
3240:
3213:
3189:
3167:
3101:
3067:
3033:
3032:{\displaystyle \log k}
3005:
3004:{\displaystyle \log n}
2971:
2928:
2895:On the more realistic
2881:
2836:
2775:
2753:
2752:{\displaystyle 2.942n}
2730:
2704:
2676:
2629:
2608:
2588:
2557:
2514:
2467:
2434:
2401:
2370:
2342:
2320:
2247:
2216:
2209:
2178:
2122:
2076:
2043:
2012:
1948:
1928:
1895:
1873:
1857:Floyd–Rivest algorithm
1845:
1823:
1800:
1778:
1742:
1721:
1681:
1642:
1601:
1566:
1546:
1518:
1494:
1473:
1429:
1405:
1382:
1359:
1314:
1290:
1266:
1243:
1205:
1183:
1162:
1142:
1122:
1088:
1052:
1030:
990:
968:
946:
898:
859:
830:
792:
748:
725:
688:
669:Sorting and heapselect
653:
608:
570:
550:
528:
472:
450:
422:
398:
368:
334:
282:floating-point numbers
266:
244:
221:
190:
151:
118:
73:
52:
7452:10.1145/366622.366647
7358:10.1145/235767.235772
7337:
7311:
7289:
7244:
7182:
7105:
7006:Journal of Algorithms
6869:
6854:(1999). "Finding the
6771:Mitzenmacher, Michael
6764:
6654:Journal of Algorithms
6443:
6229:(8). Wiley: 983–993.
6156:10.1145/174130.174132
6037:Rinnooy Kan, A. H. G.
6014:10.1145/355694.355704
5988:10.1145/360680.360694
5977:
5955:
5926:10.1145/360680.360691
5845:Devroye, Luc (2001).
5811:Devroye, Luc (1984).
5489:Leiserson, Charles E.
5307:
5271:
5233:
5177:
5156:
5136:
5121:, limited to holding
5076:
5051:
4919:
4896:
4873:
4850:
4829:
4809:
4781:
4760:
4740:
4712:
4695:
4656:
4612:
4505:
4424:
4385:
4356:
4294:
4272:
4242:
4187:
4152:
4132:
4108:
4106:{\displaystyle n+p-2}
4076:
4050:
4024:
3998:
3978:
3947:
3921:
3895:
3871:
3834:
3806:
3786:
3759:
3739:
3707:
3670:
3632:
3597:
3542:
3505:
3453:
3415:
3393:
3354:
3293:
3262:
3241:
3239:{\displaystyle k_{i}}
3214:
3190:
3168:
3102:
3068:
3034:
3006:
2972:
2929:
2887:steps, matching this
2882:
2837:
2776:
2754:
2731:
2705:
2677:
2630:
2609:
2589:
2558:
2515:
2468:
2435:
2433:{\displaystyle 9n/10}
2402:
2400:{\displaystyle 7n/10}
2371:
2343:
2321:
2248:
2210:
2208:{\displaystyle 3n/10}
2179:
2177:{\displaystyle 3n/10}
2147:
2123:
2077:
2044:
2013:
1949:
1929:
1896:
1874:
1846:
1824:
1801:
1779:
1743:
1722:
1682:
1643:
1602:
1567:
1547:
1519:
1495:
1474:
1430:
1406:
1383:
1360:
1315:
1291:
1267:
1244:
1206:
1184:
1163:
1143:
1123:
1089:
1087:{\displaystyle k=n/2}
1053:
1031:
991:
969:
947:
899:
860:
831:
793:
749:
726:
689:
654:
609:
607:{\displaystyle k=n/2}
571:
551:
529:
473:
451:
423:
399:
369:
335:
302:arithmetic operations
267:
245:
222:
191:
152:
119:
74:
53:
7512:Selection algorithms
7320:
7300:
7278:
7233:
7156:
7091:
6977:10.1109/FOCS.2014.26
6858:
6747:
6411:
6131:Karloff, Howard J.;
5966:
5944:
5780:Goodrich, Michael T.
5296:
5242:
5186:
5166:
5145:
5125:
5065:
4965:
4908:
4885:
4862:
4839:
4818:
4792:
4770:
4749:
4729:
4668:
4630:
4514:
4435:
4413:
4383:{\displaystyle o(n)}
4365:
4303:
4283:
4261:
4200:
4163:
4141:
4121:
4085:
4059:
4033:
4007:
3987:
3967:
3930:
3904:
3884:
3869:{\displaystyle O(n)}
3851:
3815:
3795:
3772:
3748:
3728:
3681:
3659:
3648:order statistic tree
3608:
3552:
3516:
3494:
3424:
3404:
3391:{\displaystyle O(k)}
3373:
3274:
3251:
3223:
3203:
3199:For a collection of
3179:
3114:
3085:
3057:
3017:
2989:
2938:
2903:
2850:
2805:
2765:
2740:
2714:
2688:
2666:
2619:
2598:
2578:
2556:{\displaystyle O(n)}
2538:
2513:{\displaystyle O(n)}
2495:
2466:{\displaystyle O(n)}
2448:
2413:
2380:
2352:
2332:
2258:
2229:
2188:
2157:
2090:
2053:
2042:{\displaystyle o(n)}
2024:
1960:
1938:
1927:{\displaystyle rk/n}
1907:
1885:
1863:
1835:
1810:
1790:
1777:{\displaystyle O(n)}
1759:
1732:
1711:
1680:{\displaystyle O(n)}
1662:
1616:
1600:{\displaystyle O(n)}
1582:
1556:
1536:
1508:
1484:
1441:
1419:
1395:
1372:
1327:
1304:
1280:
1256:
1217:
1195:
1173:
1152:
1132:
1106:
1064:
1042:
1002:
980:
958:
912:
888:
849:
820:
764:
738:
715:
678:
623:
584:
560:
540:
492:
462:
434:
412:
382:
352:
344:zero-based numbering
318:
298:comparison operation
290:model of computation
256:
234:
211:
189:{\displaystyle O(1)}
171:
150:{\displaystyle O(n)}
132:
108:
63:
42:
7466:Dodgson, Charles L.
7335:{\displaystyle i,n}
7121:10.1145/22145.22169
7052:(2): A26:1–A26:16.
6762:{\displaystyle X+Y}
6573:(4): A38:1–A38:11.
6487:Pippenger, Nicholas
6200:1992ITEdu..35..230G
6133:Raghavan, Prabhakar
5982:elements", p. 173,
5439:10.1145/62044.62047
4807:{\displaystyle n=1}
4510:comparisons, where
4074:{\displaystyle p-1}
4048:{\displaystyle n-1}
4022:{\displaystyle p-1}
3945:{\displaystyle n-1}
3919:{\displaystyle n-1}
3722:streaming algorithm
3269:array, the time is
2795:Parallel algorithms
2790:Parallel algorithms
2729:{\displaystyle n-k}
2703:{\displaystyle k-1}
2369:{\displaystyle n/5}
2328:Thus, a problem on
2246:{\displaystyle n/5}
1121:{\displaystyle n-1}
1060:such as the choice
998:but degenerates to
449:{\displaystyle k=n}
397:{\displaystyle k=1}
367:{\displaystyle k=1}
333:{\displaystyle k=0}
157:as expressed using
32:selection algorithm
7332:
7306:
7284:
7239:
7224:Hadian, Abdollah;
7177:
7103:{\displaystyle 2n}
7100:
6864:
6759:
6693:Johnson, Donald B.
6438:
6403:; Steiger, W. L.;
6357:Valiant, Leslie G.
6142:Journal of the ACM
6060:10.1145/182.358440
5972:
5950:
5425:Journal of the ACM
5302:
5266:
5228:
5172:
5151:
5131:
5071:
5046:
4914:
4891:
4868:
4845:
4824:
4804:
4776:
4755:
4735:
4720:
4690:
4651:
4607:
4500:
4419:
4380:
4351:
4299:requires at least
4289:
4267:
4237:
4182:
4147:
4127:
4115:adversary argument
4103:
4071:
4045:
4019:
3993:
3973:
3942:
3916:
3890:
3866:
3829:
3801:
3781:
3754:
3734:
3702:
3665:
3640:iterated logarithm
3627:
3592:
3537:
3500:
3479:implicitly defined
3448:
3410:
3388:
3349:
3257:
3236:
3209:
3185:
3163:
3097:
3063:
3029:
3001:
2967:
2924:
2877:
2832:
2771:
2749:
2726:
2700:
2672:
2625:
2604:
2594:that are far from
2584:
2553:
2510:
2485:divide and conquer
2463:
2430:
2397:
2366:
2338:
2316:
2243:
2217:
2205:
2174:
2118:
2072:
2039:
2008:
1944:
1924:
1891:
1869:
1841:
1822:{\displaystyle Cn}
1819:
1796:
1774:
1738:
1717:
1677:
1638:
1597:
1562:
1542:
1514:
1490:
1469:
1425:
1413:smallest value is
1401:
1378:
1355:
1310:
1286:
1274:smallest value is
1262:
1239:
1201:
1179:
1158:
1138:
1118:
1084:
1048:
1036:for larger values
1026:
986:
974:is small relative
964:
954:This is fast when
942:
906:smallest value in
894:
855:
826:
788:
744:
721:
684:
649:
604:
566:
546:
524:
468:
446:
418:
394:
364:
330:
262:
240:
217:
186:
147:
114:
69:
48:
7309:{\displaystyle n}
7287:{\displaystyle i}
7242:{\displaystyle t}
7002:Muthukrishnan, S.
7000:Cormode, Graham;
6986:978-1-4799-6517-5
6874:shortest paths".
6867:{\displaystyle k}
6637:978-3-540-57182-7
6208:10.1109/13.144650
5975:{\displaystyle n}
5953:{\displaystyle i}
5903:Rivest, Ronald L.
5797:978-1-118-33591-8
5784:Tamassia, Roberto
5710:978-3-642-40272-2
5640:Tarjan, Robert E.
5636:Rivest, Ronald L.
5601:. pp. 35–39.
5556:978-3-030-54255-9
5535:Skiena, Steven S.
5493:Rivest, Ronald L.
5485:Cormen, Thomas H.
5342:median of medians
5305:{\displaystyle k}
5175:{\displaystyle k}
5154:{\displaystyle k}
5134:{\displaystyle k}
5074:{\displaystyle k}
4917:{\displaystyle k}
4894:{\displaystyle k}
4871:{\displaystyle k}
4848:{\displaystyle k}
4827:{\displaystyle n}
4779:{\displaystyle n}
4758:{\displaystyle k}
4738:{\displaystyle n}
4605:
4556:
4495:
4431:element requires
4422:{\displaystyle k}
4292:{\displaystyle n}
4270:{\displaystyle k}
4150:{\displaystyle p}
4130:{\displaystyle p}
3996:{\displaystyle p}
3976:{\displaystyle p}
3893:{\displaystyle n}
3804:{\displaystyle k}
3757:{\displaystyle k}
3737:{\displaystyle n}
3668:{\displaystyle k}
3503:{\displaystyle k}
3461:best-first search
3413:{\displaystyle n}
3260:{\displaystyle i}
3212:{\displaystyle m}
3188:{\displaystyle k}
3066:{\displaystyle k}
2774:{\displaystyle k}
2675:{\displaystyle k}
2628:{\displaystyle n}
2607:{\displaystyle 1}
2587:{\displaystyle k}
2341:{\displaystyle n}
2222:median of medians
2150:median of medians
2113:
2067:
1947:{\displaystyle k}
1894:{\displaystyle r}
1872:{\displaystyle r}
1844:{\displaystyle C}
1799:{\displaystyle C}
1786:For any constant
1741:{\displaystyle R}
1720:{\displaystyle L}
1565:{\displaystyle R}
1545:{\displaystyle L}
1517:{\displaystyle R}
1493:{\displaystyle R}
1428:{\displaystyle R}
1404:{\displaystyle k}
1381:{\displaystyle k}
1313:{\displaystyle L}
1289:{\displaystyle L}
1265:{\displaystyle k}
1204:{\displaystyle k}
1182:{\displaystyle k}
1161:{\displaystyle R}
1141:{\displaystyle L}
1051:{\displaystyle k}
989:{\displaystyle n}
967:{\displaystyle k}
897:{\displaystyle k}
858:{\displaystyle k}
829:{\displaystyle k}
747:{\displaystyle k}
724:{\displaystyle k}
687:{\displaystyle k}
569:{\displaystyle k}
549:{\displaystyle n}
471:{\displaystyle n}
421:{\displaystyle n}
304:on these values.
265:{\displaystyle k}
243:{\displaystyle k}
220:{\displaystyle k}
201:Problem statement
117:{\displaystyle n}
102:median of medians
72:{\displaystyle k}
51:{\displaystyle k}
7519:
7496:
7495:
7473:
7462:
7456:
7455:
7430:
7424:
7423:
7421:
7420:
7405:
7399:
7393:
7391:
7390:
7376:
7370:
7369:
7341:
7339:
7338:
7333:
7315:
7313:
7312:
7307:
7295:
7293:
7291:
7290:
7285:
7271:Gasarch, William
7267:
7261:
7260:
7250:
7248:
7246:
7245:
7240:
7221:
7215:
7214:
7186:
7184:
7183:
7178:
7142:
7136:
7135:
7123:
7109:
7107:
7106:
7101:
7084:
7078:
7077:
7040:Chan, Timothy M.
7036:
7030:
7029:
6997:
6991:
6990:
6970:
6951:
6945:
6944:
6908:
6902:
6901:
6873:
6871:
6870:
6865:
6848:
6842:
6841:
6831:
6805:
6799:
6798:
6796:
6786:
6768:
6766:
6765:
6760:
6736:
6723:
6722:
6688:
6679:
6678:
6648:
6642:
6641:
6629:
6605:
6599:
6598:
6560:
6554:
6553:
6523:
6517:
6516:
6482:
6476:
6475:
6447:
6445:
6444:
6439:
6405:Szemerédi, Endre
6393:
6387:
6386:
6353:
6347:
6346:
6321:(5): 1722–1758.
6301:
6295:
6294:
6245:
6239:
6238:
6218:
6212:
6211:
6183:
6177:
6176:
6158:
6128:
6122:
6121:
6102:Knuth, Donald E.
6098:
6081:
6080:
6062:
6035:Postmus, J. T.;
6032:
6026:
6025:
5997:
5991:
5981:
5979:
5978:
5973:
5961:
5959:
5957:
5956:
5951:
5938:
5928:
5899:Floyd, Robert W.
5895:
5886:
5885:
5851:
5843:
5817:
5808:
5802:
5801:
5776:
5763:
5760:
5754:
5753:
5740:Algorithm Design
5728:
5715:
5714:
5685:
5679:
5678:
5668:
5648:
5628:Floyd, Robert W.
5620:
5603:
5602:
5592:
5577:
5576:
5531:
5518:
5516:
5481:
5460:
5459:
5441:
5411:
5375:
5339:
5332:
5315:
5311:
5309:
5308:
5303:
5291:
5287:
5275:
5273:
5272:
5267:
5237:
5235:
5234:
5229:
5181:
5179:
5178:
5173:
5160:
5158:
5157:
5152:
5140:
5138:
5137:
5132:
5116:
5112:
5102:
5087:Language support
5082:
5080:
5078:
5077:
5072:
5055:
5053:
5052:
5047:
5042:
5041:
5011:
5010:
5001:
5000:
4934:1 1
4928:
4925:
4923:
4921:
4920:
4915:
4902:
4900:
4898:
4897:
4892:
4879:
4877:
4875:
4874:
4869:
4856:
4854:
4852:
4851:
4846:
4834:values, and the
4833:
4831:
4830:
4825:
4813:
4811:
4810:
4805:
4787:
4785:
4783:
4782:
4777:
4764:
4762:
4761:
4756:
4744:
4742:
4741:
4736:
4701:
4699:
4697:
4696:
4691:
4689:
4688:
4662:
4660:
4658:
4657:
4652:
4623:
4616:
4614:
4613:
4608:
4606:
4604:
4590:
4585:
4584:
4557:
4549:
4544:
4543:
4509:
4507:
4506:
4501:
4496:
4491:
4477:
4476:
4464:
4444:
4443:
4430:
4428:
4426:
4425:
4420:
4405:
4397:
4389:
4387:
4386:
4381:
4360:
4358:
4357:
4352:
4298:
4296:
4295:
4290:
4278:
4276:
4274:
4273:
4268:
4253:
4252:6.5 comparisons.
4248:
4246:
4244:
4243:
4238:
4221:
4220:
4193:
4191:
4189:
4188:
4183:
4175:
4174:
4156:
4154:
4153:
4148:
4136:
4134:
4133:
4128:
4113:comparisons. An
4112:
4110:
4109:
4104:
4080:
4078:
4077:
4072:
4054:
4052:
4051:
4046:
4028:
4026:
4025:
4020:
4002:
4000:
3999:
3994:
3982:
3980:
3979:
3974:
3961:Sergey Kislitsyn
3956:
3951:
3949:
3948:
3943:
3925:
3923:
3922:
3917:
3900:values requires
3899:
3897:
3896:
3891:
3875:
3873:
3872:
3867:
3838:
3836:
3835:
3830:
3825:
3810:
3808:
3807:
3802:
3790:
3788:
3787:
3782:
3766:count–min sketch
3763:
3761:
3760:
3755:
3743:
3741:
3740:
3735:
3719:
3715:
3711:
3709:
3708:
3703:
3676:
3674:
3672:
3671:
3666:
3643:
3636:
3634:
3633:
3628:
3620:
3619:
3603:
3601:
3599:
3598:
3593:
3570:
3569:
3546:
3544:
3543:
3538:
3511:
3509:
3507:
3506:
3501:
3484:
3470:
3464:
3457:
3455:
3454:
3449:
3419:
3417:
3416:
3411:
3399:
3397:
3395:
3394:
3389:
3360:
3358:
3356:
3355:
3350:
3348:
3347:
3332:
3331:
3312:
3307:
3286:
3285:
3268:
3266:
3264:
3263:
3258:
3245:
3243:
3242:
3237:
3235:
3234:
3218:
3216:
3215:
3210:
3198:
3194:
3192:
3191:
3186:
3174:
3172:
3170:
3169:
3164:
3162:
3161:
3149:
3126:
3125:
3108:
3106:
3104:
3103:
3098:
3078:
3074:
3072:
3070:
3069:
3064:
3040:
3038:
3036:
3035:
3030:
3010:
3008:
3007:
3002:
2984:
2980:
2976:
2974:
2973:
2968:
2954:
2933:
2931:
2930:
2925:
2894:
2890:
2886:
2884:
2883:
2878:
2845:
2841:
2839:
2838:
2833:
2786:
2782:
2780:
2778:
2777:
2772:
2758:
2756:
2755:
2750:
2735:
2733:
2732:
2727:
2709:
2707:
2706:
2701:
2683:
2681:
2679:
2678:
2673:
2655:
2643:Arnold Schönhage
2636:
2634:
2632:
2631:
2626:
2613:
2611:
2610:
2605:
2593:
2591:
2590:
2585:
2565:
2562:
2560:
2559:
2554:
2527:
2523:
2519:
2517:
2516:
2511:
2490:
2482:
2478:
2474:
2472:
2470:
2469:
2464:
2441:
2439:
2437:
2436:
2431:
2426:
2406:
2404:
2403:
2398:
2393:
2375:
2373:
2372:
2367:
2362:
2347:
2345:
2344:
2339:
2327:
2325:
2323:
2322:
2317:
2312:
2295:
2287:
2279:
2271:
2252:
2250:
2249:
2244:
2239:
2214:
2212:
2211:
2206:
2201:
2183:
2181:
2180:
2175:
2170:
2131:
2127:
2125:
2124:
2119:
2114:
2100:
2085:
2081:
2079:
2078:
2073:
2068:
2063:
2048:
2046:
2045:
2040:
2019:
2017:
2015:
2014:
2009:
1953:
1951:
1950:
1945:
1933:
1931:
1930:
1925:
1920:
1902:
1900:
1898:
1897:
1892:
1878:
1876:
1875:
1870:
1852:
1850:
1848:
1847:
1842:
1828:
1826:
1825:
1820:
1805:
1803:
1802:
1797:
1785:
1783:
1781:
1780:
1775:
1749:
1747:
1745:
1744:
1739:
1726:
1724:
1723:
1718:
1701:prune and search
1693:
1688:
1686:
1684:
1683:
1678:
1655:geometric series
1649:
1647:
1645:
1644:
1639:
1634:
1633:
1608:
1606:
1604:
1603:
1598:
1575:
1571:
1569:
1568:
1563:
1551:
1549:
1548:
1543:
1525:
1523:
1521:
1520:
1515:
1501:
1499:
1497:
1496:
1491:
1478:
1476:
1475:
1470:
1462:
1454:
1436:
1434:
1432:
1431:
1426:
1412:
1410:
1408:
1407:
1402:
1389:
1387:
1385:
1384:
1379:
1366:
1364:
1362:
1361:
1356:
1348:
1340:
1321:
1319:
1317:
1316:
1311:
1297:
1295:
1293:
1292:
1287:
1273:
1271:
1269:
1268:
1263:
1250:
1248:
1246:
1245:
1240:
1238:
1230:
1210:
1208:
1207:
1202:
1190:
1188:
1186:
1185:
1180:
1167:
1165:
1164:
1159:
1147:
1145:
1144:
1139:
1127:
1125:
1124:
1119:
1093:
1091:
1090:
1085:
1080:
1059:
1057:
1055:
1054:
1049:
1035:
1033:
1032:
1027:
997:
995:
993:
992:
987:
973:
971:
970:
965:
953:
951:
949:
948:
943:
905:
903:
901:
900:
895:
874:
866:
864:
862:
861:
856:
837:
835:
833:
832:
827:
813:
804:
797:
795:
794:
789:
755:
753:
751:
750:
745:
732:
730:
728:
727:
722:
695:
693:
691:
690:
685:
660:
658:
656:
655:
650:
639:
613:
611:
610:
605:
600:
575:
573:
572:
567:
555:
553:
552:
547:
535:
533:
531:
530:
525:
520:
477:
475:
474:
469:
457:
455:
453:
452:
447:
427:
425:
424:
419:
405:
403:
401:
400:
395:
375:
373:
371:
370:
365:
341:
339:
337:
336:
331:
310:
271:
269:
268:
263:
251:
249:
247:
246:
241:
228:
226:
224:
223:
218:
197:
195:
193:
192:
187:
156:
154:
153:
148:
123:
121:
120:
115:
80:
78:
76:
75:
70:
57:
55:
54:
49:
38:for finding the
28:computer science
7527:
7526:
7522:
7521:
7520:
7518:
7517:
7516:
7502:
7501:
7500:
7499:
7492:
7463:
7459:
7434:Hoare, C. A. R.
7431:
7427:
7418:
7416:
7407:
7406:
7402:
7388:
7386:
7378:
7377:
7373:
7345:ACM SIGACT News
7321:
7318:
7317:
7301:
7298:
7297:
7279:
7276:
7275:
7274:
7268:
7264:
7234:
7231:
7230:
7229:
7222:
7218:
7157:
7154:
7153:
7143:
7139:
7132:
7092:
7089:
7088:
7085:
7081:
7037:
7033:
6998:
6994:
6987:
6955:Pătraşcu, Mihai
6952:
6948:
6909:
6905:
6859:
6856:
6855:
6852:Eppstein, David
6849:
6845:
6806:
6802:
6748:
6745:
6744:
6737:
6726:
6711:10.1137/0213002
6689:
6682:
6649:
6645:
6638:
6606:
6602:
6561:
6557:
6542:10.1137/0214030
6524:
6520:
6483:
6479:
6412:
6409:
6408:
6394:
6390:
6375:10.1137/0204030
6354:
6350:
6302:
6298:
6246:
6242:
6219:
6215:
6184:
6180:
6129:
6125:
6118:
6099:
6084:
6053:(11): 878–881.
6033:
6029:
5998:
5994:
5967:
5964:
5963:
5945:
5942:
5941:
5940:
5896:
5889:
5849:
5815:
5809:
5805:
5798:
5777:
5766:
5761:
5757:
5750:
5729:
5718:
5711:
5686:
5682:
5646:
5621:
5606:
5593:
5580:
5557:
5532:
5521:
5513:
5497:Stein, Clifford
5482:
5463:
5414:Cunto, Walter;
5412:
5405:
5400:
5381:
5373:
5350:Robert W. Floyd
5334:
5330:
5321:
5313:
5297:
5294:
5293:
5289:
5285:
5243:
5240:
5239:
5187:
5184:
5183:
5167:
5164:
5163:
5146:
5143:
5142:
5126:
5123:
5122:
5114:
5111:heapq.nsmallest
5110:
5100:
5089:
5066:
5063:
5062:
5061:
5037:
5036:
5006:
5002:
4996:
4995:
4966:
4963:
4962:
4959:
4956:
4953:
4950:
4947:
4944:
4941:
4938:
4935:
4932:
4926:
4909:
4906:
4905:
4904:
4886:
4883:
4882:
4881:
4863:
4860:
4859:
4858:
4840:
4837:
4836:
4835:
4819:
4816:
4815:
4793:
4790:
4789:
4771:
4768:
4767:
4766:
4750:
4747:
4746:
4730:
4727:
4726:
4707:
4681:
4677:
4669:
4666:
4665:
4664:
4631:
4628:
4627:
4625:
4618:
4594:
4589:
4580:
4576:
4548:
4539:
4535:
4515:
4512:
4511:
4490:
4472:
4471:
4460:
4439:
4438:
4436:
4433:
4432:
4414:
4411:
4410:
4409:
4403:
4400:Yao's principle
4395:
4366:
4363:
4362:
4304:
4301:
4300:
4284:
4281:
4280:
4279:element out of
4262:
4259:
4258:
4257:
4251:
4216:
4212:
4201:
4198:
4197:
4195:
4170:
4166:
4164:
4161:
4160:
4158:
4142:
4139:
4138:
4122:
4119:
4118:
4086:
4083:
4082:
4060:
4057:
4056:
4034:
4031:
4030:
4008:
4005:
4004:
3988:
3985:
3984:
3968:
3965:
3964:
3954:
3931:
3928:
3927:
3905:
3902:
3901:
3885:
3882:
3881:
3852:
3849:
3848:
3845:
3821:
3816:
3813:
3812:
3796:
3793:
3792:
3773:
3770:
3769:
3749:
3746:
3745:
3729:
3726:
3725:
3717:
3713:
3682:
3679:
3678:
3660:
3657:
3656:
3655:
3638:
3615:
3611:
3609:
3606:
3605:
3565:
3561:
3553:
3550:
3549:
3548:
3517:
3514:
3513:
3495:
3492:
3491:
3490:
3482:
3468:
3459:
3425:
3422:
3421:
3405:
3402:
3401:
3374:
3371:
3370:
3368:
3343:
3342:
3327:
3323:
3308:
3297:
3281:
3280:
3275:
3272:
3271:
3270:
3252:
3249:
3248:
3247:
3230:
3226:
3224:
3221:
3220:
3204:
3201:
3200:
3196:
3180:
3177:
3176:
3175:or faster when
3157:
3156:
3145:
3121:
3120:
3115:
3112:
3111:
3110:
3086:
3083:
3082:
3080:
3076:
3058:
3055:
3054:
3053:
3046:
3018:
3015:
3014:
3012:
2990:
2987:
2986:
2982:
2978:
2950:
2939:
2936:
2935:
2904:
2901:
2900:
2892:
2888:
2851:
2848:
2847:
2843:
2806:
2803:
2802:
2792:
2784:
2766:
2763:
2762:
2760:
2741:
2738:
2737:
2715:
2712:
2711:
2689:
2686:
2685:
2667:
2664:
2663:
2662:
2650:
2620:
2617:
2616:
2614:
2599:
2596:
2595:
2579:
2576:
2575:
2572:
2563:
2539:
2536:
2535:
2525:
2521:
2496:
2493:
2492:
2488:
2480:
2476:
2449:
2446:
2445:
2443:
2422:
2414:
2411:
2410:
2408:
2389:
2381:
2378:
2377:
2358:
2353:
2350:
2349:
2333:
2330:
2329:
2308:
2291:
2283:
2275:
2267:
2259:
2256:
2255:
2254:
2235:
2230:
2227:
2226:
2197:
2189:
2186:
2185:
2166:
2158:
2155:
2154:
2129:
2099:
2091:
2088:
2087:
2083:
2062:
2054:
2051:
2050:
2025:
2022:
2021:
1961:
1958:
1957:
1956:
1939:
1936:
1935:
1916:
1908:
1905:
1904:
1886:
1883:
1882:
1880:
1864:
1861:
1860:
1836:
1833:
1832:
1830:
1811:
1808:
1807:
1791:
1788:
1787:
1760:
1757:
1756:
1754:
1733:
1730:
1729:
1727:
1712:
1709:
1708:
1691:
1663:
1660:
1659:
1657:
1629:
1625:
1617:
1614:
1613:
1611:
1583:
1580:
1579:
1577:
1573:
1557:
1554:
1553:
1537:
1534:
1533:
1509:
1506:
1505:
1503:
1485:
1482:
1481:
1479:
1458:
1450:
1442:
1439:
1438:
1420:
1417:
1416:
1414:
1396:
1393:
1392:
1391:
1373:
1370:
1369:
1368:
1344:
1336:
1328:
1325:
1324:
1322:
1305:
1302:
1301:
1299:
1281:
1278:
1277:
1275:
1257:
1254:
1253:
1252:
1234:
1226:
1218:
1215:
1214:
1212:
1196:
1193:
1192:
1174:
1171:
1170:
1169:
1153:
1150:
1149:
1133:
1130:
1129:
1107:
1104:
1103:
1100:
1076:
1065:
1062:
1061:
1043:
1040:
1039:
1037:
1003:
1000:
999:
981:
978:
977:
975:
959:
956:
955:
913:
910:
909:
907:
889:
886:
885:
884:
872:
850:
847:
846:
845:
821:
818:
817:
815:
811:
807:integer sorting
801:comparison sort
799:
765:
762:
761:
739:
736:
735:
734:
716:
713:
712:
711:
710:, retrieve its
679:
676:
675:
674:
671:
666:
635:
624:
621:
620:
619:
596:
585:
582:
581:
561:
558:
557:
541:
538:
537:
516:
493:
490:
489:
487:
463:
460:
459:
435:
432:
431:
429:
413:
410:
409:
383:
380:
379:
378:
353:
350:
349:
347:
319:
316:
315:
313:
308:
294:comparison sort
257:
254:
253:
235:
232:
231:
230:
229:It outputs the
212:
209:
208:
206:
203:
172:
169:
168:
166:
133:
130:
129:
109:
106:
105:
82:order statistic
64:
61:
60:
59:
43:
40:
39:
24:
17:
12:
11:
5:
7525:
7515:
7514:
7498:
7497:
7490:
7457:
7446:(7): 321–322.
7425:
7400:
7384:Python library
7371:
7331:
7328:
7325:
7305:
7283:
7262:
7238:
7216:
7197:(3): 312–325.
7187:comparisons".
7176:
7173:
7170:
7167:
7164:
7161:
7137:
7130:
7099:
7096:
7079:
7031:
6992:
6985:
6946:
6919:(4): 637–646.
6903:
6884:(2): 652–673.
6863:
6843:
6822:(2): 197–214.
6800:
6758:
6755:
6752:
6724:
6680:
6643:
6636:
6600:
6555:
6536:(2): 396–409.
6518:
6499:(1–2): 49–58.
6477:
6458:(1): 125–133.
6437:
6434:
6431:
6428:
6425:
6422:
6419:
6416:
6388:
6369:(3): 348–355.
6348:
6296:
6269:(2): 184–199.
6240:
6213:
6194:(3): 230–232.
6178:
6149:(3): 454–476.
6123:
6116:
6082:
6027:
6008:(3): 301–304.
5992:
5971:
5949:
5919:(3): 165–172.
5905:(March 1975).
5887:
5860:(3): 291–303.
5803:
5796:
5764:
5755:
5748:
5732:Kleinberg, Jon
5716:
5709:
5680:
5659:(4): 448–461.
5632:Pratt, Vaughan
5604:
5578:
5555:
5519:
5511:
5461:
5432:(2): 270–279.
5402:
5401:
5399:
5396:
5395:
5394:
5388:
5380:
5377:
5370:Hugo Steinhaus
5320:
5317:
5301:
5265:
5262:
5259:
5256:
5253:
5250:
5247:
5227:
5224:
5221:
5218:
5215:
5212:
5209:
5206:
5203:
5200:
5197:
5194:
5191:
5171:
5150:
5130:
5115:heapq.nlargest
5088:
5085:
5070:
5045:
5040:
5035:
5032:
5029:
5026:
5023:
5020:
5017:
5014:
5009:
5005:
4999:
4994:
4991:
4988:
4985:
4982:
4979:
4976:
4973:
4970:
4957:
4954:
4951:
4948:
4945:
4942:
4939:
4936:
4933:
4930:
4913:
4890:
4867:
4844:
4823:
4803:
4800:
4797:
4775:
4754:
4734:
4706:
4703:
4687:
4684:
4680:
4676:
4673:
4650:
4647:
4644:
4641:
4638:
4635:
4603:
4600:
4597:
4593:
4588:
4583:
4579:
4575:
4572:
4569:
4566:
4563:
4560:
4555:
4552:
4547:
4542:
4538:
4534:
4531:
4528:
4525:
4522:
4519:
4499:
4494:
4489:
4486:
4483:
4480:
4475:
4470:
4467:
4463:
4459:
4456:
4453:
4450:
4447:
4442:
4418:
4379:
4376:
4373:
4370:
4350:
4347:
4344:
4341:
4338:
4335:
4332:
4329:
4326:
4323:
4320:
4317:
4314:
4311:
4308:
4288:
4266:
4236:
4233:
4230:
4227:
4224:
4219:
4215:
4211:
4208:
4205:
4181:
4178:
4173:
4169:
4146:
4126:
4102:
4099:
4096:
4093:
4090:
4070:
4067:
4064:
4044:
4041:
4038:
4018:
4015:
4012:
3992:
3972:
3941:
3938:
3935:
3915:
3912:
3909:
3889:
3865:
3862:
3859:
3856:
3844:
3841:
3828:
3824:
3820:
3800:
3780:
3777:
3753:
3733:
3701:
3698:
3695:
3692:
3689:
3686:
3664:
3626:
3623:
3618:
3614:
3591:
3588:
3585:
3582:
3579:
3576:
3573:
3568:
3564:
3560:
3557:
3536:
3533:
3530:
3527:
3524:
3521:
3499:
3487:priority queue
3471:shortest paths
3447:
3444:
3441:
3438:
3435:
3432:
3429:
3409:
3387:
3384:
3381:
3378:
3346:
3341:
3338:
3335:
3330:
3326:
3322:
3319:
3316:
3311:
3306:
3303:
3300:
3296:
3292:
3289:
3284:
3279:
3256:
3233:
3229:
3208:
3184:
3160:
3155:
3152:
3148:
3144:
3141:
3138:
3135:
3132:
3129:
3124:
3119:
3096:
3093:
3090:
3062:
3050:data structure
3045:
3042:
3028:
3025:
3022:
3000:
2997:
2994:
2966:
2963:
2960:
2957:
2953:
2949:
2946:
2943:
2923:
2920:
2917:
2914:
2911:
2908:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2831:
2828:
2825:
2822:
2819:
2816:
2813:
2810:
2799:Leslie Valiant
2791:
2788:
2770:
2748:
2745:
2725:
2722:
2719:
2699:
2696:
2693:
2671:
2658:partial orders
2652:Nick Pippenger
2624:
2603:
2583:
2571:
2568:
2567:
2566:
2552:
2549:
2546:
2543:
2528:
2509:
2506:
2503:
2500:
2462:
2459:
2456:
2453:
2429:
2425:
2421:
2418:
2396:
2392:
2388:
2385:
2365:
2361:
2357:
2337:
2315:
2311:
2307:
2304:
2301:
2298:
2294:
2290:
2286:
2282:
2278:
2274:
2270:
2266:
2263:
2242:
2238:
2234:
2204:
2200:
2196:
2193:
2173:
2169:
2165:
2162:
2142:
2141:
2117:
2112:
2109:
2106:
2103:
2098:
2095:
2071:
2066:
2061:
2058:
2038:
2035:
2032:
2029:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1943:
1923:
1919:
1915:
1912:
1890:
1868:
1853:
1840:
1818:
1815:
1795:
1773:
1770:
1767:
1764:
1737:
1716:
1694:
1676:
1673:
1670:
1667:
1637:
1632:
1628:
1624:
1621:
1596:
1593:
1590:
1587:
1561:
1541:
1513:
1489:
1468:
1465:
1461:
1457:
1453:
1449:
1446:
1424:
1400:
1377:
1354:
1351:
1347:
1343:
1339:
1335:
1332:
1309:
1285:
1261:
1237:
1233:
1229:
1225:
1222:
1200:
1178:
1157:
1137:
1117:
1114:
1111:
1099:
1096:
1083:
1079:
1075:
1072:
1069:
1047:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
985:
963:
941:
938:
935:
932:
929:
926:
923:
920:
917:
893:
854:
842:selection sort
825:
787:
784:
781:
778:
775:
772:
769:
758:
757:
743:
720:
704:
703:the collection
683:
670:
667:
665:
662:
648:
645:
642:
638:
634:
631:
628:
603:
599:
595:
592:
589:
565:
545:
523:
519:
515:
512:
509:
506:
503:
500:
497:
467:
445:
442:
439:
417:
393:
390:
387:
363:
360:
357:
329:
326:
323:
261:
239:
216:
202:
199:
185:
182:
179:
176:
159:big O notation
146:
143:
140:
137:
113:
68:
47:
15:
9:
6:
4:
3:
2:
7524:
7513:
7510:
7509:
7507:
7493:
7491:9780192549013
7487:
7483:
7479:
7471:
7467:
7461:
7453:
7449:
7445:
7441:
7440:
7435:
7429:
7414:
7410:
7404:
7397:
7385:
7381:
7375:
7367:
7363:
7359:
7355:
7351:
7347:
7346:
7329:
7326:
7323:
7303:
7281:
7272:
7266:
7258:
7254:
7236:
7227:
7226:Sobel, Milton
7220:
7212:
7208:
7204:
7200:
7196:
7192:
7191:
7174:
7168:
7165:
7162:
7151:
7147:
7141:
7133:
7131:0-89791-151-2
7127:
7122:
7117:
7113:
7097:
7094:
7083:
7075:
7071:
7067:
7063:
7059:
7055:
7051:
7047:
7046:
7041:
7035:
7027:
7023:
7019:
7015:
7011:
7007:
7003:
6996:
6988:
6982:
6978:
6974:
6969:
6964:
6960:
6956:
6950:
6942:
6938:
6934:
6930:
6926:
6922:
6918:
6914:
6907:
6899:
6895:
6891:
6887:
6883:
6879:
6878:
6861:
6853:
6847:
6839:
6835:
6830:
6825:
6821:
6817:
6816:
6811:
6804:
6795:
6790:
6785:
6780:
6776:
6772:
6756:
6753:
6750:
6742:
6735:
6733:
6731:
6729:
6720:
6716:
6712:
6708:
6704:
6700:
6699:
6694:
6687:
6685:
6676:
6672:
6668:
6664:
6660:
6656:
6655:
6647:
6639:
6633:
6628:
6623:
6619:
6615:
6611:
6604:
6596:
6592:
6588:
6584:
6580:
6576:
6572:
6568:
6567:
6559:
6551:
6547:
6543:
6539:
6535:
6531:
6530:
6522:
6514:
6510:
6506:
6502:
6498:
6494:
6493:
6488:
6485:Azar, Yossi;
6481:
6473:
6469:
6465:
6461:
6457:
6453:
6452:
6432:
6429:
6426:
6423:
6420:
6414:
6406:
6402:
6401:Komlós, János
6398:
6397:Ajtai, Miklós
6392:
6384:
6380:
6376:
6372:
6368:
6364:
6363:
6358:
6352:
6344:
6340:
6336:
6332:
6328:
6324:
6320:
6316:
6315:
6310:
6306:
6300:
6292:
6288:
6284:
6280:
6276:
6272:
6268:
6264:
6263:
6258:
6257:Pippenger, N.
6254:
6250:
6249:Schönhage, A.
6244:
6236:
6232:
6228:
6224:
6217:
6209:
6205:
6201:
6197:
6193:
6189:
6182:
6174:
6170:
6166:
6162:
6157:
6152:
6148:
6144:
6143:
6138:
6134:
6127:
6119:
6117:0-201-89685-0
6113:
6109:
6108:
6103:
6097:
6095:
6093:
6091:
6089:
6087:
6078:
6074:
6070:
6066:
6061:
6056:
6052:
6048:
6047:
6042:
6038:
6031:
6023:
6019:
6015:
6011:
6007:
6003:
5996:
5989:
5985:
5969:
5947:
5936:
5932:
5927:
5922:
5918:
5914:
5913:
5908:
5904:
5900:
5894:
5892:
5883:
5879:
5875:
5871:
5867:
5863:
5859:
5855:
5848:
5841:
5837:
5833:
5829:
5825:
5821:
5814:
5807:
5799:
5793:
5789:
5785:
5781:
5775:
5773:
5771:
5769:
5759:
5751:
5749:9780321295354
5745:
5741:
5737:
5733:
5727:
5725:
5723:
5721:
5712:
5706:
5702:
5698:
5694:
5690:
5684:
5676:
5672:
5667:
5662:
5658:
5654:
5653:
5645:
5641:
5637:
5633:
5629:
5625:
5619:
5617:
5615:
5613:
5611:
5609:
5600:
5599:
5591:
5589:
5587:
5585:
5583:
5574:
5570:
5566:
5562:
5558:
5552:
5548:
5544:
5540:
5536:
5530:
5528:
5526:
5524:
5514:
5512:0-262-03384-4
5508:
5504:
5503:
5498:
5494:
5490:
5486:
5480:
5478:
5476:
5474:
5472:
5470:
5468:
5466:
5457:
5453:
5449:
5445:
5440:
5435:
5431:
5427:
5426:
5421:
5417:
5416:Munro, J. Ian
5410:
5408:
5403:
5392:
5391:Median filter
5389:
5386:
5383:
5382:
5376:
5374:comparisons).
5371:
5367:
5366:Lewis Carroll
5363:
5362:Robert Tarjan
5359:
5355:
5354:Vaughan Pratt
5351:
5347:
5343:
5337:
5329:
5325:
5316:
5299:
5284:has included
5283:
5278:
5260:
5257:
5254:
5251:
5245:
5222:
5219:
5216:
5213:
5210:
5204:
5201:
5198:
5189:
5169:
5148:
5128:
5120:
5108:
5104:
5098:
5094:
5084:
5068:
5059:
5043:
5030:
5027:
5024:
5021:
5018:
5012:
5007:
5003:
4989:
4986:
4983:
4977:
4974:
4971:
4968:
4929:
4911:
4888:
4865:
4842:
4821:
4801:
4798:
4795:
4773:
4752:
4732:
4724:
4716:
4715:Hasse diagram
4711:
4702:
4685:
4682:
4678:
4674:
4671:
4648:
4642:
4639:
4636:
4621:
4601:
4598:
4595:
4591:
4586:
4581:
4577:
4570:
4567:
4564:
4558:
4553:
4550:
4545:
4540:
4536:
4532:
4529:
4523:
4517:
4492:
4481:
4478:
4465:
4461:
4457:
4451:
4448:
4445:
4416:
4406:
4401:
4394:of the input
4393:
4374:
4368:
4345:
4339:
4336:
4330:
4327:
4324:
4321:
4318:
4309:
4306:
4286:
4264:
4254:
4234:
4231:
4225:
4222:
4217:
4213:
4206:
4203:
4179:
4176:
4171:
4167:
4144:
4124:
4116:
4100:
4097:
4094:
4091:
4088:
4068:
4065:
4062:
4042:
4039:
4036:
4016:
4013:
4010:
3990:
3970:
3962:
3957:
3939:
3936:
3933:
3913:
3910:
3907:
3887:
3878:
3860:
3854:
3840:
3826:
3822:
3818:
3798:
3778:
3775:
3767:
3751:
3731:
3723:
3696:
3693:
3690:
3684:
3662:
3653:
3649:
3644:
3641:
3624:
3621:
3616:
3612:
3586:
3583:
3580:
3577:
3574:
3571:
3566:
3562:
3555:
3531:
3528:
3525:
3519:
3497:
3488:
3480:
3476:
3472:
3462:
3442:
3439:
3436:
3433:
3427:
3407:
3382:
3376:
3366:
3361:
3336:
3333:
3328:
3324:
3317:
3314:
3309:
3304:
3301:
3298:
3294:
3290:
3287:
3277:
3254:
3231:
3227:
3206:
3182:
3150:
3146:
3142:
3139:
3133:
3130:
3127:
3117:
3094:
3091:
3088:
3060:
3051:
3041:
3026:
3023:
3020:
2998:
2995:
2992:
2961:
2958:
2955:
2951:
2947:
2941:
2918:
2915:
2912:
2906:
2898:
2871:
2868:
2865:
2862:
2859:
2853:
2826:
2823:
2820:
2817:
2814:
2800:
2796:
2787:
2768:
2746:
2743:
2723:
2720:
2717:
2697:
2694:
2691:
2669:
2659:
2653:
2648:
2647:Mike Paterson
2644:
2640:
2622:
2601:
2581:
2547:
2541:
2533:
2529:
2504:
2498:
2486:
2457:
2451:
2427:
2423:
2419:
2416:
2394:
2390:
2386:
2383:
2363:
2359:
2355:
2335:
2313:
2309:
2305:
2302:
2299:
2288:
2280:
2272:
2240:
2236:
2232:
2223:
2219:
2218:
2202:
2198:
2194:
2191:
2171:
2167:
2163:
2160:
2151:
2146:
2139:
2135:
2110:
2107:
2104:
2101:
2093:
2064:
2056:
2033:
2027:
2002:
1996:
1993:
1987:
1984:
1981:
1978:
1975:
1966:
1963:
1941:
1921:
1917:
1913:
1910:
1888:
1866:
1858:
1854:
1838:
1816:
1813:
1793:
1768:
1762:
1753:
1752:expected time
1735:
1714:
1706:
1702:
1698:
1695:
1671:
1665:
1656:
1652:
1651:
1650:
1630:
1626:
1619:
1591:
1585:
1559:
1539:
1531:
1526:
1511:
1487:
1466:
1463:
1455:
1447:
1444:
1422:
1398:
1375:
1352:
1349:
1341:
1333:
1330:
1307:
1283:
1259:
1231:
1223:
1220:
1198:
1176:
1155:
1135:
1115:
1112:
1109:
1095:
1081:
1077:
1073:
1070:
1067:
1045:
1020:
1017:
1014:
1011:
1005:
983:
961:
936:
933:
930:
927:
924:
921:
915:
891:
882:
879:produces the
878:
870:
852:
843:
838:
823:
808:
802:
798:time using a
782:
779:
776:
773:
741:
718:
709:
705:
702:
699:
698:
697:
681:
661:
646:
643:
640:
636:
632:
629:
626:
617:
601:
597:
593:
590:
587:
579:
563:
543:
521:
517:
510:
507:
504:
498:
495:
485:
481:
465:
443:
440:
437:
415:
406:
391:
388:
385:
361:
358:
355:
345:
327:
324:
321:
305:
303:
299:
295:
291:
287:
283:
279:
275:
259:
237:
214:
198:
180:
174:
164:
160:
141:
135:
127:
111:
103:
99:
95:
91:
87:
83:
66:
45:
37:
33:
29:
22:
7481:
7469:
7460:
7443:
7437:
7428:
7417:. Retrieved
7412:
7403:
7387:. Retrieved
7383:
7374:
7352:(2): 88–96.
7349:
7343:
7265:
7257:11299/199105
7219:
7194:
7188:
7140:
7111:
7082:
7049:
7043:
7034:
7012:(1): 58–75.
7009:
7005:
6995:
6958:
6949:
6916:
6912:
6906:
6881:
6875:
6846:
6819:
6813:
6803:
6774:
6705:(1): 14–30.
6702:
6696:
6661:(1): 33–51.
6658:
6652:
6646:
6609:
6603:
6570:
6564:
6558:
6533:
6527:
6521:
6496:
6490:
6480:
6455:
6449:
6391:
6366:
6360:
6351:
6318:
6312:
6299:
6266:
6260:
6253:Paterson, M.
6243:
6226:
6222:
6216:
6191:
6187:
6181:
6146:
6140:
6126:
6106:
6050:
6044:
6030:
6005:
6001:
5995:
5962:smallest of
5916:
5910:
5857:
5854:Algorithmica
5853:
5823:
5819:
5806:
5787:
5758:
5739:
5692:
5683:
5656:
5650:
5624:Blum, Manuel
5597:
5538:
5501:
5429:
5423:
5336:Donald Knuth
5322:
5280:Since 2017,
5279:
5105:
5090:
5058:Milton Sobel
4960:
4721:
4407:
4392:permutations
4255:
3958:
3879:
3846:
3843:Lower bounds
3645:
3362:
3047:
2897:parallel RAM
2893:comparisons.
2793:
2638:
2573:
2489:subproblems.
1574:represented.
1527:
1101:
839:
759:
672:
616:upper median
615:
578:lower median
577:
407:
306:
204:
31:
25:
7415:. Mathworks
7296:largest of
5736:Tardos, Éva
5346:Manuel Blum
5324:Quickselect
5119:binary heap
5101:nth_element
3650:augments a
3475:state space
3365:binary heap
3197:dimensions.
2979:processors.
2532:introselect
2477:randomized.
2084:questioned.
1697:Quickselect
126:linear time
98:quickselect
7419:2023-03-30
7389:2023-08-06
7316:for small
7150:Zwick, Uri
7146:Dor, Dorit
6784:1802.07041
6741:Zwick, Uri
6309:Zwick, Uri
6305:Dor, Dorit
5826:(1): 1–7.
5598:Algorithms
5398:References
5358:Ron Rivest
5328:Tony Hoare
3714:operation.
3512:item from
881:heapselect
805:Even when
664:Algorithms
480:odd number
100:, and the
7474:See also
7169:ε
6968:1408.3045
6941:253740380
6430:
6424:
5258:
5220:
5202:−
5028:−
5013:
4987:−
4972:−
4683:−
4675:≈
4672:ε
4643:ε
4626:at least
4599:−
4587:
4568:−
4546:
4485:Ω
4337:−
4328:−
4232:−
4229:⌉
4223:
4210:⌈
4177:
4159:at least
4098:−
4066:−
4040:−
4014:−
3937:−
3911:−
3827:ε
3791:steps of
3776:ε
3712:time per
3694:
3622:
3617:∗
3584:
3572:
3567:∗
3529:
3440:
3318:
3295:∑
3134:
3092:×
3024:
2996:
2959:
2916:
2869:
2863:
2824:
2818:
2809:Ω
2721:−
2695:−
2639:factories
2570:Factories
2522:practice,
2300:≤
2128:for this
2108:
1985:−
1705:quicksort
1530:quicksort
1464:−
1448:−
1367:then the
1224:≤
1113:−
1018:
934:
780:
768:Θ
36:algorithm
7506:Category
7468:(1883).
7074:11742607
6773:(eds.).
6291:29867292
6173:17956460
6135:(1993).
6022:13985011
5642:(1973).
5573:22382667
5456:10947879
5418:(1989).
5379:See also
5331:in 1965,
5314:time is.
5039:⌉
4998:⌈
4927:largest.
3955:maximum.
3718:allowed.
2985:and the
2983:general,
2844:maximum.
2785:smaller.
1098:Pivoting
877:heapsort
756:element.
614:and the
488:setting
430:setting
348:setting
314:setting
292:, as in
278:integers
7366:3133332
7211:1857348
7066:2675693
7026:2132028
6933:3942251
6898:1634364
6838:1221889
6719:0731024
6675:1661179
6595:9645870
6587:2364962
6550:0784745
6513:1055590
6472:0990052
6383:0378467
6343:2633282
6335:1694164
6283:0428794
6196:Bibcode
6165:1370358
6077:3211474
6069:0784120
5935:3064709
5874:1855252
5840:0761047
5675:0329916
5565:4241430
5448:1072421
5319:History
4718:median.
4617:is the
4396:values.
3637:is the
873:method.
207:number
94:maximum
86:minimum
7488:
7364:
7209:
7128:
7072:
7064:
7024:
6983:
6939:
6931:
6896:
6836:
6717:
6673:
6634:
6593:
6585:
6548:
6511:
6470:
6381:
6341:
6333:
6289:
6281:
6171:
6163:
6114:
6075:
6067:
6020:
5933:
5882:674040
5880:
5872:
5838:
5794:
5746:
5707:
5673:
5571:
5563:
5553:
5509:
5454:
5446:
5360:, and
5290:mink()
5286:maxk()
5282:Matlab
5107:Python
4404:input.
4157:to be
3367:takes
2889:bound.
2649:, and
2481:known,
484:median
482:, the
478:is an
342:as in
309:other,
286:object
165:takes
92:, and
90:median
34:is an
7362:S2CID
7070:S2CID
6963:arXiv
6937:S2CID
6779:arXiv
6591:S2CID
6339:S2CID
6287:S2CID
6169:S2CID
6073:S2CID
6018:S2CID
5931:S2CID
5878:S2CID
5850:(PDF)
5816:(PDF)
5647:(PDF)
5569:S2CID
5452:S2CID
4723:Knuth
3604:here
3483:tree.
3369:time
3081:size
3077:time.
2934:with
2744:2.942
2564:time.
2526:size.
2409:most
2130:term.
1881:size
1692:call.
908:time
812:time.
708:array
618:with
580:with
536:When
458:When
167:time
163:array
7486:ISBN
7126:ISBN
6981:ISBN
6632:ISBN
6112:ISBN
5792:ISBN
5744:ISBN
5705:ISBN
5551:ISBN
5507:ISBN
5288:and
5113:and
5095:for
4745:and
4663:for
3847:The
3744:and
2220:The
1855:The
1728:and
1552:and
1251:the
701:Sort
274:sort
30:, a
7448:doi
7354:doi
7342:".
7253:hdl
7249:-th
7199:doi
7116:doi
7054:doi
7014:doi
6973:doi
6921:doi
6886:doi
6824:doi
6820:104
6789:doi
6707:doi
6663:doi
6622:hdl
6614:doi
6575:doi
6538:doi
6501:doi
6460:doi
6448:".
6427:log
6421:log
6371:doi
6323:doi
6271:doi
6231:doi
6204:doi
6151:doi
6055:doi
6010:doi
5984:doi
5921:doi
5862:doi
5828:doi
5697:doi
5661:doi
5543:doi
5434:doi
5255:log
5217:log
5097:C++
5004:log
4578:log
4537:log
4398:By
4313:min
4214:log
4196:is
4168:log
3691:log
3613:log
3581:log
3563:log
3547:to
3526:log
3437:log
3315:log
3131:log
3021:log
3013:by
2993:log
2956:log
2913:log
2866:log
2860:log
2821:log
2815:log
2761:of
2615:or
2444:to
2262:max
2105:log
1970:min
1831:in
1755:is
1658:to
1612:as
1578:is
1504:in
1480:of
1415:in
1323:If
1300:to
1276:in
1213:if
1038:of
1015:log
976:to
931:log
816:of
777:log
26:In
7508::
7480:.
7442:.
7411:.
7382:.
7360:.
7350:27
7348:.
7294:th
7207:MR
7205:.
7195:14
7193:.
7148:;
7124:.
7068:.
7062:MR
7060:.
7048:.
7022:MR
7020:.
7010:55
7008:.
6979:.
6971:.
6935:.
6929:MR
6927:.
6917:63
6915:.
6894:MR
6892:.
6882:28
6880:.
6834:MR
6832:.
6818:.
6812:.
6787:.
6727:^
6715:MR
6713:.
6703:13
6701:.
6683:^
6671:MR
6669:.
6659:30
6657:.
6630:.
6620:.
6589:.
6583:MR
6581:.
6569:.
6546:MR
6544:.
6534:14
6532:.
6509:MR
6507:.
6497:27
6495:.
6468:MR
6466:.
6456:38
6454:.
6399:;
6379:MR
6377:.
6365:.
6337:.
6331:MR
6329:.
6319:28
6317:.
6307:;
6285:.
6279:MR
6277:.
6267:13
6265:.
6255:;
6251:;
6227:27
6225:.
6202:.
6192:35
6190:.
6167:.
6161:MR
6159:.
6147:40
6145:.
6139:.
6085:^
6071:.
6065:MR
6063:.
6051:26
6049:.
6043:.
6016:.
6004:.
5960:th
5929:.
5917:18
5915:.
5909:.
5901:;
5890:^
5876:.
5870:MR
5868:.
5858:31
5856:.
5852:.
5836:MR
5834:.
5824:29
5822:.
5818:.
5782:;
5767:^
5734:;
5719:^
5703:.
5671:MR
5669:.
5655:.
5649:.
5638:;
5634:;
5630:;
5626:;
5607:^
5581:^
5567:.
5561:MR
5559:.
5549:.
5522:^
5495:;
5491:;
5487:;
5464:^
5450:.
5444:MR
5442:.
5430:36
5428:.
5422:.
5406:^
5356:,
5352:,
5348:,
5081:th
4924:th
4901:th
4878:th
4855:th
4786:th
4686:80
4429:th
4277:th
3839:.
3675:th
3510:th
3267:th
3073:th
2682:th
2645:,
2428:10
2395:10
2314:10
2203:10
2172:10
1411:th
1388:th
1272:th
1189:th
904:th
865:th
754:th
731:th
694:th
280:,
250:th
128:,
88:,
79:th
7494:.
7454:.
7450::
7444:4
7422:.
7398:.
7392:.
7368:.
7356::
7330:n
7327:,
7324:i
7304:n
7282:i
7259:.
7255::
7237:t
7213:.
7201::
7175:N
7172:)
7166:+
7163:2
7160:(
7134:.
7118::
7098:n
7095:2
7076:.
7056::
7050:6
7028:.
7016::
6989:.
6975::
6965::
6943:.
6923::
6900:.
6888::
6862:k
6840:.
6826::
6797:.
6791::
6781::
6757:Y
6754:+
6751:X
6721:.
6709::
6677:.
6665::
6640:.
6624::
6616::
6597:.
6577::
6571:3
6552:.
6540::
6515:.
6503::
6474:.
6462::
6436:)
6433:n
6418:(
6415:O
6385:.
6373::
6367:4
6345:.
6325::
6293:.
6273::
6237:.
6233::
6210:.
6206::
6198::
6175:.
6153::
6120:.
6079:.
6057::
6024:.
6012::
6006:2
5990:.
5986::
5970:n
5948:i
5937:.
5923::
5884:.
5864::
5842:.
5830::
5800:.
5752:.
5713:.
5699::
5677:.
5663::
5657:7
5575:.
5545::
5515:.
5458:.
5436::
5338:.
5300:k
5264:)
5261:k
5252:n
5249:(
5246:O
5226:)
5223:k
5214:k
5211:+
5208:)
5205:k
5199:n
5196:(
5193:(
5190:O
5170:k
5149:k
5129:k
5069:k
5044:.
5034:)
5031:k
5025:2
5022:+
5019:n
5016:(
5008:2
4993:)
4990:1
4984:k
4981:(
4978:+
4975:k
4969:n
4931:0
4912:k
4889:k
4866:k
4843:k
4822:n
4802:1
4799:=
4796:n
4774:n
4753:k
4733:n
4700:.
4679:2
4661:,
4649:n
4646:)
4640:+
4637:2
4634:(
4622:.
4602:x
4596:1
4592:1
4582:2
4574:)
4571:x
4565:1
4562:(
4559:+
4554:x
4551:1
4541:2
4533:x
4530:=
4527:)
4524:x
4521:(
4518:H
4498:)
4493:n
4488:(
4482:+
4479:n
4474:)
4469:)
4466:n
4462:/
4458:k
4455:(
4452:H
4449:+
4446:1
4441:(
4417:k
4378:)
4375:n
4372:(
4369:o
4349:)
4346:1
4343:(
4340:O
4334:)
4331:k
4325:n
4322:,
4319:k
4316:(
4310:+
4307:n
4287:n
4265:k
4247:,
4235:2
4226:n
4218:2
4207:+
4204:n
4192:.
4180:n
4172:2
4145:p
4125:p
4101:2
4095:p
4092:+
4089:n
4069:1
4063:p
4043:1
4037:n
4017:1
4011:p
3991:p
3971:p
3940:1
3934:n
3914:1
3908:n
3888:n
3864:)
3861:n
3858:(
3855:O
3823:/
3819:1
3799:k
3779:n
3752:k
3732:n
3700:)
3697:n
3688:(
3685:O
3663:k
3642:.
3625:n
3602:;
3590:)
3587:k
3578:+
3575:n
3559:(
3556:O
3535:)
3532:n
3523:(
3520:O
3498:k
3469:k
3463:.
3446:)
3443:n
3434:k
3431:(
3428:O
3408:n
3398:.
3386:)
3383:k
3380:(
3377:O
3359:.
3345:)
3340:)
3337:1
3334:+
3329:i
3325:k
3321:(
3310:m
3305:1
3302:=
3299:i
3291:+
3288:m
3283:(
3278:O
3255:i
3232:i
3228:k
3207:m
3183:k
3173:,
3159:)
3154:)
3151:m
3147:/
3143:n
3140:2
3137:(
3128:m
3123:(
3118:O
3107:,
3095:n
3089:m
3061:k
3039:.
3027:k
2999:n
2965:)
2962:n
2952:/
2948:n
2945:(
2942:O
2922:)
2919:n
2910:(
2907:O
2875:)
2872:n
2857:(
2854:O
2830:)
2827:n
2812:(
2781:,
2769:k
2747:n
2724:k
2718:n
2698:1
2692:k
2670:k
2654:.
2635:,
2623:n
2602:1
2582:k
2551:)
2548:n
2545:(
2542:O
2508:)
2505:n
2502:(
2499:O
2473:.
2461:)
2458:n
2455:(
2452:O
2440:,
2424:/
2420:n
2417:9
2391:/
2387:n
2384:7
2364:5
2360:/
2356:n
2336:n
2326:.
2310:/
2306:n
2303:7
2297:)
2293:|
2289:R
2285:|
2281:,
2277:|
2273:L
2269:|
2265:(
2241:5
2237:/
2233:n
2199:/
2195:n
2192:3
2168:/
2164:n
2161:3
2116:)
2111:n
2102:n
2097:(
2094:O
2070:)
2065:n
2060:(
2057:O
2037:)
2034:n
2031:(
2028:o
2018:.
2006:)
2003:n
2000:(
1997:o
1994:+
1991:)
1988:k
1982:n
1979:,
1976:k
1973:(
1967:+
1964:n
1942:k
1922:n
1918:/
1914:k
1911:r
1901:,
1889:r
1867:r
1851:.
1839:C
1817:n
1814:C
1794:C
1784:.
1772:)
1769:n
1766:(
1763:O
1748:,
1736:R
1715:L
1687:.
1675:)
1672:n
1669:(
1666:O
1648:.
1636:)
1631:2
1627:n
1623:(
1620:O
1607:.
1595:)
1592:n
1589:(
1586:O
1560:R
1540:L
1524:.
1512:R
1500:.
1488:R
1467:1
1460:|
1456:L
1452:|
1445:k
1435:,
1423:R
1399:k
1376:k
1365:,
1353:1
1350:+
1346:|
1342:L
1338:|
1334:=
1331:k
1320:.
1308:L
1296:,
1284:L
1260:k
1249:,
1236:|
1232:L
1228:|
1221:k
1199:k
1177:k
1156:R
1136:L
1116:1
1110:n
1082:2
1078:/
1074:n
1071:=
1068:k
1058:,
1046:k
1024:)
1021:n
1012:n
1009:(
1006:O
996:,
984:n
962:k
952:.
940:)
937:n
928:k
925:+
922:n
919:(
916:O
892:k
853:k
836:.
824:k
803:.
786:)
783:n
774:n
771:(
742:k
719:k
682:k
659:.
647:1
644:+
641:2
637:/
633:n
630:=
627:k
602:2
598:/
594:n
591:=
588:k
564:k
544:n
534:.
522:2
518:/
514:)
511:1
508:+
505:n
502:(
499:=
496:k
466:n
456:.
444:n
441:=
438:k
416:n
404:.
392:1
389:=
386:k
374:,
362:1
359:=
356:k
340:,
328:0
325:=
322:k
260:k
238:k
227:.
215:k
196:.
184:)
181:1
178:(
175:O
145:)
142:n
139:(
136:O
112:n
67:k
46:k
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.