/** find the Middle element in the Array without sorting it. * This function uses a modified version of QuickSort, where we * only consider the one half of the array. * This is a recursive function where we look at some section of the array * (Concerned Array) at a time. * * @param low = Loweset index of the Concerned Array * @param high = Heighest index of the Concerned Array * @param mid= The middle of the element in concerned array mid = (high-low)/2 */
int findMedian(int *arr, int low, int high, int mid){ int pivot = low; int l=low; int h = high; if(l<=h){ while(l<h){ while(arr[l]<=arr[pivot]) l++; while(arr[h]>arr[pivot]) h--; if(l<h){ // Swapping the left and right int temp = arr[l]; arr[l] = arr[h]; arr[h] = temp; } } // Swapping the pivot with the high pointer int temp = arr[pivot] ; arr[pivot] = arr[h]; arr[h] = temp; } if(mid< h){ return findElementAtRank(arr, low, h-1, mid); }else if(rank > h ){ return findElementAtRank(arr, h+1, high, mid); }else{ return arr[h]; } } On Tue, Jul 27, 2010 at 12:15 PM, Avik Mitra <tutai...@gmail.com> wrote: > Given that the list is in sorted order. Let us assume that the list in > the form of an array A[1...n]. > > Case 1: If n is odd. Then the median is A[(n+1)/2]. Set MEDIAN:=A[(n > +1)/2. > Case 2: If n is even. Then the median is (A[n/2]+ A[n/2 +1])/2. Set > MEDIAN:=(A[n/2]+ A[n/2 +1])/2. > > Assuming that the array accessing, the addition and division takes > O(1) time. The running time of the algorithm is O(1). > > On Jul 26, 1:15 pm, Manjunath Manohar <manjunath.n...@gmail.com> > wrote: >> @Anand...for better efficiency..we can find the pivot as a random >> integer..for better worst case complexity.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards, Shafi Ahmad The difficult we do immediately, the impossible takes a little longer....US Army -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.