Please ignore my previus mail as there was some typo mistake.
/** 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 findMedian(arr, low, h-1, mid);
}else if(rank > h ){
return findMedian(arr, h+1, high, mid);
}else{
return arr[h];
}
On Tue, Jul 27, 2010 at 1:33 PM, Shafi Ahmad <[email protected]> wrote:
> /** 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
>
--
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.
