Median of the array

Purdue_Pete
Purdue_Pete used Ask the Experts™
on
Hi,
I have been looking at various programming questions, one of them being able to find median of the array as indicated in 3rd page (top) of the handout here:
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Handout_2.pdf

How can this done
a) with quicksort
b) without quicksort?

Please post code in any language for both of them.
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Quick-sort is for sorting the content of an array. After the array is sorted finding the median is very simple:

array_name[numbers_in_array / 2];

Without sorting your array, you can do it, by calculating for every element the numbers of values smaller then it, and the values greater then it. If these two numbers are both less then half of the size of the array, this element is the median:

//this code is in C#
List<int> list;
//
//Read the content of the list
//
for( int i = 0; i < list.Count; i++ )
             int smaller = 0, larger = 0;
             for( int p = 0; p < l.Count; p++ )
                   if( list[p] < list[i] )
                         smaller++;
                   else if( list[i] < list[p] )
                         larger++;
             if( smaller < list.Count/2 && larger < list.Coun/2 )
                   return list[i]];

If every element of this array are different, the variable smaller and larger will be equal to k if the size of the array is 2*k+1.
Is this an academic assignment? If so, EE is limited in how we may respond. In particular, we cannot provide code for you if you are required to do that yourself. Please let us know. If you provide code and are having trouble, then you can ask for assistance on the specific problems that you note.

Here are two algorithms to find the median in an unsorted array w/o using any sorting algorithm. You can copy the pseudo-code from the pdf Lecture Notes:
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed06.htm
Learn SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

Author

Commented:
All,
I am looking for code or reference to code that is better than O(n log n). Quick sort average is O(n log n).

Sinistra_D32: Thanks for the explanation and  code.

melchkishore: Thanks for the reference.

phoffric: No, this has got nothing to do with academic assignments. I am just trying to review and update my algorithms skill. I happen to come across the document as explained in the question - found to be very helpful as a quick start guide.

In the link you provide in your question, it says that finding the kth element is O(n). Then it says:

"Note that finding the median of an array is a special case of this where k = n / 2.This is a very important point, as an interviewer will often ask you to find a way toget the median of an array of numbers."

Do you think this is implying that finding a median is O(n). The above quote is sort of suggesting that. Do you think this is so?

How did you like the contents in the link in http:#26446399 ?

Author

Commented:
phoffric,
Here the entire array has to be sorted which is essentially quick sort on the entire array. Hence, it is O(n log n). O(n) applied to searching for an element which is a different problem - they are searching half of an array recursively!

The link helped - they seem to find the median in linear time.

Thanks!

> the entire array has to be sorted which is essentially quick sort onthe entire array. "Hence, it is O(n log n). O(n) applied to searchingfor an element which is a different problem"

If you are talking about your reference, then here is my take on your reference:"To do this, you select a random pivot and partition the array as you would in the quicksort algorithm."

The above quote does not say: using the quicksort algorithm, but rather "as your would".
 
So, the reference you provided implied that you start off with a quicksort-like algorithm, e.g., by using an "index of the pivot element" but then instead of applying quicksort to both halves only one half needs to be processed. So, this reference is not saying to do a quicksort O(nlogn) followed by the selection (which on a sorted array is o(1)).  

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial