The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

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.

Implementations

  • Standard Template library in C++ form SGI (C++) (rating 10)
  • Java Collections (Java) (rating 9)
  • Handbook of Algorithms and Data Structures (C,Pascal) (rating 5)
  • Xtango and Polka Algorithm Animation Systems (C++,C) (rating 3)

    • Recommended Books

    Data Streams: Algorithms and Applications by S. Muthukrishnan The Art of Computer Programming : Sorting and Searching by Donald Knuth Compared to What? by G. Rawlins
    Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein Combinatorial Search by M. Aigner Computer Algorithms by S. Baase
    The Design and Analysis of Computer Algorithms by A. Aho and J. Hopcroft and J. Ullman

    Related Problems
    Priority Queues
    Sorting


    This page last modified on 2008-07-10 .
    www.algorist.com