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 92●1●4●8 accept rate: 0%

 22 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
 2 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; }  answered 03 Jul '13, 18:09 2★panicker 31●1●4 accept rate: 0%
 0 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 answered 16 Jan '16, 23:03 1 accept rate: 0%
 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]
 0 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 0★ntloi95 1 accept rate: 0%
 0 Use std::nth_element answered 14 Aug '17, 12:14 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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