Medians and Order Statistics

If A = <a₁, a₂, a₃, ...,a_n>

length [A] = n

Sorted <a₁¢, a₂¢, a₃¢, ...,a_n¢>
where    a₁¢  £  a₂¢  £  a₃ ¢£  ...£   a_n¢

a_i¢ = i^th order statistic

a₁¢ = first order statistic (minimum)

a_n¢ = n^th order statistic (maximum)

"middle guy" « median

( n + 1 ) / 2 = i  n odd

n/2 and n/2 + 1 = i n even

i = ë ( n + 1 ) / 2 û and é ( n + 1 ) / 2 ù

Assume distinct values for the a_i¢ : a₁¢  £  a₂¢  £  a₃ ¢£  ...£   a_n

Selection Problem

Input : A (n distinct), 1 £ i £ n

Output : a_i¢ (element of A larger than exactly i - 1 other elements of A).

Best Algorithms we know:

User heap sort or merge sort to sort in O ( (n lg n )) time and index a_i¢ . We can do better than O (( n) ), we'll see how now.

Minimum and Maximum

Using comparisons can find the minimum in at most n - 1 comparisons:

Minimum (A)

1. min ¬ A[1]

2. for i ¬ 2 to length[A] = n ( for loop executed  n- 1 times )

3.    do if min > A[i]

4.       then min ¬ A[i]  ( Q  ( lg n ) )times

5. return min

If we desire both maximum and minimum we can add max A ¬ [1] and comparisons to 2 n - 2 comparisons for both. We can get away with 3  é n / 2 ù comparisons by ( A[i],  A[ i+1] ) taking pairs and comparing those and minimum/maximum of those are compared with running values. There are three compares per tow elements of A.