kth Smallest Member Selection Algorithm

See: Sorting Algorithm, Sample Median.

---

---

References

2013

• http://en.wikipedia.org/wiki/Selection_algorithm
  • In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are [math]\displaystyle{ O(n) }[/math], worst-case linear time, selection algorithms. Selection is a subproblem of more complex problems like the nearest neighbor problem and shortest path problems.
• http://en.wikipedia.org/wiki/Selection_algorithm#Selection_by_sorting
  • Selection can be reduced to sorting by sorting the list and then extracting the desired element. This method is efficient when many selections need to be made from a list, in which case only one initial, expensive sort is needed, followed by many cheap extraction operations. In general, this method requires O(n log n) time, where n is the length of the list.

---