/** 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 <[email protected]> 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 <[email protected]>
> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
