You are not logged in. Please login at www.codechef.com to post your questions!

×

Find Median in an Unsorted Array Without Sorting it

5
2

Given an unsorted Array A[1,2,3,.....N], Find the Medians in this array without sorting it in an efficient Way?

asked 30 Jun '12, 23:07

cpluspluscoder's gravatar image

4★cpluspluscoder
92148
accept rate: 0%


This Problem Can be done is a linear Time O(N),where N=A.length() . Yes ,Selection Algorithm Finds the Median of an unsorted Array without Sorting it.

The Selection Algorithm uses the concept of Quick Sort[But does not actually sort the array though] ,especially the partition Steps.

This algorithm works in two steps. The partitioning step works by picking some pivot element, then rearranging the elements of the array such that everything less than the pivot is to one side, everything greater than the pivot is to the other side, and the pivot is in the correct place.

In a simple words::

In a quick sort ,when you calls the Partition Function, and Lets say the partition Function returns 'Idx' , then the job of sorting 'Idx' position is Done, that is the A[Idx] contains the same element as the Idx th element of final answers (sorted Array) ,and all element to the left of 'Idx' is less than or equal to A[idx].

This is the main concept used by the selection Algorithm.

So to find the Medians basically our aim is to call recursively,the partitions functions unless the Pivot reached the N/ 2th element.

This is the implementation in C++ :

int A[MAX],N;
int partitions(int low,int high)
{
    int p=low,r=high,x=A[r],i=p-1;
    for(int j=p;j<=r-1;j++)
    {
        if (A[j]<=x)
        {

            i=i+1;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}
int selection_algorithm(int left,int right,int kth)
{
    for(;;)
    {
        int pivotIndex=partitions(left,right);          //Select the Pivot Between Left and Right
        int len=pivotIndex-left+1;

        if(kth==len)
            return A[pivotIndex];

        else if(kth<len)
            right=pivotIndex-1;

        else
        {
            kth=kth-len;
            left=pivotIndex+1;
        }
    }
}

Run this code calling the function , selection_algorithm(1,N,K),where K=N/2 (For median Elements)from the Main Function.

Note:: Using selection Algorithm ,we can't only find the Median elements without sorting , We can Find any Kth Smallest element .

Also ,note In partition Function,i selected the Pivot as the last element of Array( x=A[r] ).

You can improve the performance using the Randomized-Partition concept given in CLRS.

Hope this Helps!!!!!

link

answered 30 Jun '12, 23:25

ritesh_gupta's gravatar image

5★ritesh_gupta ♦
3.7k42549
accept rate: 27%

edited 30 Jun '12, 23:33

@ritesh_gupta :: Thanks a lot .Never thought ,there exist a linear Solution for Median Finding :)

(30 Jun '12, 23:37) cpluspluscoder4★

cpluspluscoder :)

(30 Jun '12, 23:39) ritesh_gupta ♦5★

I cannot see at first sight that this is O(n) algorithm, especially if it's inspired by quick sort where worst case is O(n^2), also "Median of Medians algorithm" is O(n), but (if I'm not wrong here) with some big constant O(C*n). When C is 20 or so, O(n*log(n)) algorithm is equally good or better for n <= 1.000.000 ...

(02 Jul '12, 15:32) betlista ♦♦3★
2

for an array of integers elements, there exists a sorting algorithm in O(n). thus, you can find the median by sorting it and keeping O(n) anyway. ( http://en.wikipedia.org/wiki/Counting_sort )

(02 Jul '12, 23:45) cyberax ♦3★

But Counting Sort is inefficient when diff b.w n and max element is really large and is almost O(N^2)so i think Selection Algo is the Best

(04 Jul '12, 11:22) cpluspluscoder4★

why is this linear? median of medians divides the whole array into groups of 5 elements then insertion sorts the subarrays...these are then used..i think ritesh your algorithm will be nlogn or since quicksort's worst case is n^2 it will be On^2 in worst case.

( http://cs.indstate.edu/~spitla/presentation.pdf )

(03 Jul '13, 18:08) panicker2★

How time complexity is O(n) ?

(06 Aug '14, 18:26) herman2★
showing 5 of 7 show all

Median of Medianshttp://cs.indstate.edu/~spitla/presentation.pdf

int select(int *a, int s, int e, int k) {
if(e-s+1 <= 5)
{
    sort(a+s, a+e);
    return s+k-1;
}

for(int i=0; i<(e+1)/5; i++)
{
    int left = 5*i;
    int right = left + 4;
    if(right > e) right = e;

    int median = select(a, left, right, 3);
    swap(a[median], a[i]);
}
return select(a, 0, (e+1)/5, (e+1)/10); }

int main() 
{  
int a[] = {6,7,8,1,2,3,4,5,9,10};
int n = 10;

int mom = select(a, 0, n-1, n/2);
cout<<"Median of Medians: " << a[mom] << endl;
return 0; }
link

answered 03 Jul '13, 18:09

panicker's gravatar image

2★panicker
3114
accept rate: 0%

edited 03 Jul '13, 18:14

it actually depends on sortedness of data

if data is sorted use medians of medians because this is worst case for normal quick select it will go in O(n^2) but med-of-med will keep worst case also in O(n) , obviously there will be some overhead of calculating pivot.

if data is partially sorted use randomised quickselect

if data is unsorted use normal quickselect (starting from first index as pivot element

choice is to choose from three methods i) medians of medians ii)randomised quickselect iii) normal quickselect

link

answered 16 Jan '16, 23:03

road_runner's gravatar image

1★road_runner
1
accept rate: 0%

median for even no fo elements (m)= (N+1)/2;(if array starts with index 1)

approch to find median without sorting array -: chose a random number(pivot) and calculate the no of elements which are greater than equal to pivot element and update right counter(r) also calculate the no of elements which are less than pivot element and update left counter(l). if l == m-1 && r == m then mth element is median.

code in c -:

int main()

{

int l,r,m,N,a[20],p;

clrscr();

l=0;

r=0;

m = N;

p = (N+1)/2;

for(i=1;i<=N-1;i++)

{

if(i == m)

continue;

else{

if(a[m]<a[i])

l++;

else

r++; }

if(l == (p-1) && r == p){

printf("median is %dth locatin %d",m,a[m]);

break;  }


 m--;
         }

return 0; }

Compelxity O(N) !

Hope this helps !

link

answered 17 Jan '16, 23:55

grv221's gravatar image

0★grv221
11
accept rate: 0%

edited 17 Jan '16, 23:58

I can explain how the code using Quicksort idea O(n) complexity. We can see, at first time run partition function, we compared n times. In average case, the array will shrink the size down to n/2 (left-right = n/2), and partition function run, we compare n/2 times.... Continue, we compared n, n/2, n/4, n/8, ... times. n, n/2, n/4, n/8 is a geometric progression with initial value = n, common ration = 1/2. SUM(n, n/2, n/4, n/8,...) = lim(t->oo) n*(1-1/2^t)/(1-1/2) = n/(1/2) = 2n. We averagely compared 2n times, so it's O(n) complexity.

link
This answer is marked "community wiki".

answered 21 Mar '17, 23:30

ntloi95's gravatar image

0★ntloi95
1
accept rate: 0%

Use std::nth_element

link

answered 14 Aug '17, 12:14

mrigendra_7's gravatar image

4★mrigendra_7
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,664
×801

question asked: 30 Jun '12, 23:07

question was seen: 102,288 times

last updated: 14 Aug '17, 12:14