Re: any relation between median and mean?

From: Gordon Sande (g.sande_at_worldnet.att.net)
Date: 06/12/04 

Date: Sat, 12 Jun 2004 15:28:43 -0300

On Fri, 11 Jun 2004 22:09:32 -0300, Brian Hetrick wrote
(in article <oY2dnR1POKpNylfdRVn-vg@comcast.com>):

> "bv" <bvoh@Xsdynamix.com> wrote ...
>> Sort the array and the median, curiously, will be in the middle of
>> the set.
>
> Truly. But there is in fact no need to sort the array: you need only
> identify the middle element.
>
> A variation on the quicksort algorithm should work. Pick a guess at the
> median, and advance in from either end of the array swapping elements when
> they are in the wrong halves. The middle element will either be where the
> two indices point, or in one of the halves. If the latter, do it again on
> the half having the median. Rinse and repeat.
>
> A full sort would be O(n log n). The algorithm sketched above would be O(n).
>

You have given a know effective algorithm but its worst case performance
is not guaranteed. There are know algorithms with guarantee worst case
performance that are also linear. Basic scheme to to lay data out in a
two way array, sort the columns and then find median of the column
medians and remove all elements _known_ to be below or above the
trial value (from the structure of the array) to get a smaller problem.
Repeat and get various details correct.

>

Relevant Pages

  • Re: Okay to move an "object" will-nilly?
    ... I wrote a funky kind of algorithm for sorting an array (whether ... the objects in the array must be move safe. ... the array was already sorted so no swaps were performed by the sort. ...
    (comp.lang.c)
  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Hash table in C++? STL?
    ... The Oalgorithm is when you scan all ... > Assume array a and b both have N elements, ... > Will a binary search beat a hash lookup? ... Running time O) for the sort if using ...
    (comp.lang.cpp)
  • Re: Sorting
    ... The easiest, probably, is to go through the array. ... This algorithm is called bubblesort. ... less efficient than selection sort or insertion sort, ... What memory management is below? ...
    (comp.lang.c)
  • Re: Sorting
    ... Then go back to the start of the array and do it again, until you make a clean sweep without swapping. ... This algorithm is called bubblesort. ... less efficient than selection sort or insertion sort, ...
    (comp.lang.c)