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

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++ :
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 RandomizedPartition concept given in CLRS. Hope this Helps!!!!! answered 30 Jun '12, 23:25
@ritesh_gupta :: Thanks a lot .Never thought ,there exist a linear Solution for Median Finding :)
(30 Jun '12, 23:37)
cpluspluscoder :)
(30 Jun '12, 23:39)
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)
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)
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)
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.
(03 Jul '13, 18:08)
How time complexity is O(n) ?
(06 Aug '14, 18:26)
showing 5 of 7
show all

Median of Medianshttp://cs.indstate.edu/~spitla/presentation.pdf
answered 03 Jul '13, 18:09

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 medofmed 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

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 == m1 && 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<=N1;i++) { if(i == m) continue; else{ if(a[m]<a[i]) l++; else r++; } if(l == (p1) && r == p){ printf("median is %dth locatin %d",m,a[m]);
return 0; } Compelxity O(N) ! Hope this helps ! answered 17 Jan '16, 23:55

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 (leftright = 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*(11/2^t)/(11/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
