Created
March 4, 2015 06:08
-
-
Save rohith2506/ff648c2f7de76bd0436d to your computer and use it in GitHub Desktop.
median of an unsorted array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Using quick sort | |
void partition(vector<int> v, int low, int high){ | |
int p=low,r=high,x=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[j+1],a[r]); | |
return i+1; // this is pivot element index | |
} | |
void median(vector<int> v){ | |
// i need to find the kth largest element where k is the median | |
// so it goes like this | |
int low = 1; | |
int high = v.size()-1; | |
if(low < high){ | |
int p = partition(v,low,p-1); | |
if(p == k) return a[p]; | |
if(p < v.size()) return median(v,low,p-1); | |
else return median(v,median,p+1, high); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment