1.3.3 Median and Selection

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A set of n numbers or keys.

Problem: Find the item which is smaller than half of the items and bigger than half the items.

Excerpt from The Algorithm Design Manual: Median finding is an essential problem in statistics, where it provides a more robust notion of average than the mean. The mean wealth of people who have published research papers on sorting is significantly affected by the presence of one William Gates [GP-75], although his effect on the {\em median} wealth is merely to cancel out one starving graduate student.

Median finding is a special case of the more general selection problem, which asks for the $i$th element in sorted order.

The best book available for this problem is The Art of Computer Programming : Sorting and Searching by Donald Knuth.


Implementations

  • Handbook of Algorithms and Data Structures (Pascal) (rating 6)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)

    Related Problems

  • Priority Queues
  • Sorting


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .