O(n) algorithm to find the median of n² implicit numbers

by

There are a number of possibilities. One I like is Hoare’s Select algorithm. The basic idea is similar to a Quicksort, except that when you recurse, you only recurse into the partition that will hold the number(s) you’re looking for.

For example, if you want the median of 100 numbers, you’d start by partitioning the array, just like in Quicksort. You’d get two partitions — one of which contains the 50th element. Recursively carry out your selection in that partition. Continue until your partition contains only one element, which will be the median (and note that you can do the same for another element of your choice).

More Related Contents:

  1. Find running median from a stream of integers
  2. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  3. Finding the median of an unsorted array
  4. How to calculate or approximate the median of a list without storing the list
  5. How do I find the median of numbers in linear time using heaps?
  6. How to find nth prime with complexity o(1)
  7. Finding all possible combinations of numbers to reach a given sum
  8. How do you rotate a two dimensional array?
  9. Equation (expression) parser with precedence?
  10. Is there an efficient way to generate N random integers in a range that have a given sum or average?
  11. Why is quicksort better than mergesort?
  12. Which sort algorithm works best on mostly sorted data? [closed]
  13. Pseudorandom Number Generator – Exponential Distribution
  14. Design patterns for converting recursive algorithms to iterative ones
  15. Natural Sorting algorithm
  16. How to delete in a heap data structure?
  17. How can I detect common substrings in a list of strings
  18. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  19. Efficiently reverse the order of the words (not characters) in an array of characters
  20. Scheduling algorithm for a round-robin tournament?
  21. How do I check if a directed graph is acyclic?
  22. Basic Recursion, Check Balanced Parenthesis
  23. How to find the smallest number with just 0 and 1 which is divided by a given number?
  24. Count the number of set bits in a 32-bit integer
  25. Find all pairs of integers within an array which sum to a specified value
  26. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  27. determine if a point sits inside an arbitrary shape?
  28. Do iterative and recursive versions of an algorithm have the same time complexity?
  29. Knapsack with multiple bags and items having only weight
  30. Tetris Piece Rotation Algorithm

Leave a Comment