Re: finding medians

ACK!  Sorting to find a median is criminal.

"Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest
ISBN: 0262031418
explains the better algorithm very well.

Here is a freely available C++ template (written by me) for a bunch of
statistics (everything *but* the selection problem):
ftp://cap.connx.com/pub/tournament_software/STATS.HPP

It uses this template for improved summation accuracy:
ftp://cap.connx.com/pub/tournament_software/Kahan.Hpp

Here is an outline for selection.  I wrote it in C++, but a rewrite to C
is trivial:

// Quickselect: find Kth smallest of first N items in array A
// recursive routine finds Kth smallest in A[Low..High]
// Etype: must have copy constructor, oeprator=, and operator<
// Nonrecursive driver is omitted.

template < class Etype >
void
QuickSelect (Etype A[], int Low, int High, int k)
{
    if (Low + Cutoff > High)
        InsertionSort (&A[Low], High - Low + 1);
    else
    {
// Sort Low, Middle, High
        int Middle = (Low + High) / 2;

        if (A[Middle] < A[Low])
            Swap (A[Low], A[Middle]);
        if (A[High] < A[Low])
            Swap (A[Low], A[High]);
        if (A[High] < A[Middle])
            Swap (A[Middle], A[High]);

// Place pivot at Position High-1
        Etype Pivot = A[Middle];
        Swap (A[Middle], A[High - 1]);

// Begin partitioning
        int i, j;
        for (i = Low, j = High - 1;;)
        {
            while (A[++i] < Pivot);
            while (Pivot < A[--j]);
            if (i < j)
                Swap (A[i], A[j]);
            else
                break;
        }

// Restore pivot
        Swap (A[i], A[High - 1]);

// Recurse: only this part changes
        if (k < i)
            QuickSelect (A, Low, i - 1, k);
        else if (k > i)
            QuickSelect (A, i + 1, High, k);
    }
}


template < class Etype >
void
QuickSelect (Etype A[], int N, int k)
{
    QuickSelect (A, 0, N - 1, k - 1);
}

If you want to use this stuff to improve statistics with vacuum, be my
guest.

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
    (send "unregister YourEmailAddressHere" to majordomo@xxxxxxxxxxxxxx)