Selection algorithm
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection.
- Comment
- enIn computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection.
- Has abstract
- enIn computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection. The simplest case of a selection algorithm is finding the minimum (or maximum) element by iterating through the list, keeping track of the running minimum – the minimum so far – (or maximum) and can be seen as related to the selection sort. Conversely, the hardest case of a selection algorithm is finding the median. In fact, a specialized median-selection algorithm can be used to build a general selection algorithm, as in median of medians. The best-known selection algorithm is Quickselect, which is related to Quicksort; like Quicksort, it has (asymptotically) optimal average performance, but poor worst-case performance, though it can be modified to give optimal worst-case performance as well.
- Hypernym
- Algorithm
- Is primary topic of
- Selection algorithm
- Label
- enSelection algorithm
- Link from a Wikipage to an external page
- www.ics.uci.edu/~eppstein/161/960125.html
- people.csail.mit.edu/rivest/pubs/BFPRT73.pdf%7C
- metacpan.org/module/Sort::Key::Top
- metacpan.org/module/Statistics::CaseResampling
- Link from a Wikipage to another Wikipage
- Algorithm
- Almost certain
- Amortized analysis
- Array data structure
- C++
- Category:Selection algorithms
- Charles E. Leiserson
- Clifford Stein
- Computer science
- Counting sort
- CPAN
- Descriptive statistics
- Divide and conquer algorithm
- Donald E. Knuth
- Donald Knuth
- Frequency tables
- Geometric series
- Hash table
- Heap (data structure)
- Introduction to Algorithms
- Introselect
- Introsort
- Lazy evaluation
- List (abstract data type)
- Matlab
- Maximum
- Median
- Median of medians
- Minimum
- Nearest neighbor problem
- Odds algorithm
- Online algorithm
- Order statistic
- Order statistic tree
- Ordinal optimization
- Partial sorting
- Perl
- Python (programming language)
- Quickselect
- Quicksort
- Radix sort
- Random access
- Range Queries
- Reduction (complexity)
- Ronald L. Rivest
- Search algorithm
- Secretary problem
- Selection sort
- Self-balancing binary search tree
- Shortest path
- Sorting algorithm
- Sublinear time
- The Art of Computer Programming
- Thomas H. Cormen
- SameAs
- 31649
- Algorisme de selecció
- Algorithme de sélection
- Algoritma seleksi
- Algoritmo de selección
- Kiválasztás (algoritmus)
- m.02p7mt
- Q3252726
- Seçim problemi
- Selection algorithm
- Алгоритм выбора
- Пошук порядкової статистики
- Селекциони алгоритам
- الگوریتم انتخاب
- خوارزمية الاختيار
- 选择算法
- 選択アルゴリズム
- 선택 알고리즘
- Subject
- Category:Selection algorithms
- WasDerivedFrom
- Selection algorithm?oldid=1110849589&ns=0
- WikiPageLength
- 22273
- Wikipage page ID
- 552786
- Wikipage revision ID
- 1110849589
- WikiPageUsesTemplate
- Template:Anchor
- Template:Citation needed
- Template:Cite journal
- Template:DADS
- Template:Expand section
- Template:For
- Template:Further
- Template:ISBN
- Template:More footnotes
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Short description