Selection Problem: Difference between revisions
| Line 8: | Line 8: | ||
<span id='Order_Statistic'></span><span id='Order_Statistics'></span>The i<sup>th</sup> '''order statistic''' of a set of n numbers is the i<sup>th</sup> smallest number in the set. | <span id='Order_Statistic'></span><span id='Order_Statistics'></span>The i<sup>th</sup> '''order statistic''' of a set of n numbers is the i<sup>th</sup> smallest number in the set. | ||
Finding the i<sup>th</sup> order statistic of a set of n ''distinct'' numbers is known as the '''selection problem'''. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element, by [[Reduction#Overview|reducing]] the selection problem to the sorting problem. However, key comparison sorting [[Comparison_Sorting_Algorithms_Complexity|cannot be done more efficiently than Ω(n lgn)]], and more specialized and faster algorithms exist. | Finding the i<sup>th</sup> order statistic of a set of n ''distinct'' numbers is known as the '''selection problem'''. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element, by [[Reduction#Overview|reducing]] the selection problem to the sorting problem. However, key comparison sorting [[Comparison_Sorting_Algorithms_Complexity|cannot be done more efficiently than Ω(n lgn)]], and more specialized and faster algorithms exist for the selection problem. | ||
The general selection problem can be resolved with a randomized divide-and-conquer algorithm with an expected running time of Θ(n). The algorithm is somewhat similar to the one used by randomized [[Quicksort#Quicksort_and_Selection_Problem|Quicksort]]. | The general selection problem can be resolved with a randomized divide-and-conquer algorithm with an expected running time of Θ(n). The algorithm is somewhat similar to the one used by randomized [[Quicksort#Quicksort_and_Selection_Problem|Quicksort]]. | ||
<font color=darkgray>TODO [[CLRS]] page 213.</font> | <font color=darkgray>TODO [[CLRS]] page 213.</font> | ||
Revision as of 23:04, 27 September 2021
Internal
Overview
The ith order statistic of a set of n numbers is the ith smallest number in the set.
Finding the ith order statistic of a set of n distinct numbers is known as the selection problem. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element, by reducing the selection problem to the sorting problem. However, key comparison sorting cannot be done more efficiently than Ω(n lgn), and more specialized and faster algorithms exist for the selection problem.
The general selection problem can be resolved with a randomized divide-and-conquer algorithm with an expected running time of Θ(n). The algorithm is somewhat similar to the one used by randomized Quicksort.
TODO CLRS page 213.