We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
void swap(int *a,int *b){
int temp=*a;
*a=*b;
*b=temp;
}
int partition(int* arr, int lower_bound, int upper_bound) {
int pivot = arr[lower_bound];
int start = lower_bound;
int end = upper_bound;
while (start < end) {
while (arr[start] <= pivot) {
start++;
}
while (arr[end] > pivot) {
end--;
}
if (start < end) {
swap(&arr[start], &arr[end]);
}
}
swap(&arr[lower_bound], &arr[end]);
return end;
}
void quick_sort(int* arr, int lower_bound, int upper_bound) {
if (lower_bound < upper_bound) {
int index = partition(arr, lower_bound, upper_bound);
quick_sort(arr, lower_bound, index - 1);
quick_sort(arr, index + 1, upper_bound);
}
}
int findMedian(int arr_count, int* arr) {
int lower_bound = 0;
int upper_bound = arr_count - 1;
quick_sort(arr, lower_bound, upper_bound);
return arr[arr_count/2];
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Find the Median
You are viewing a single comment's thread. Return to all comments →
void swap(int *a,int *b){ int temp=*a; *a=*b; *b=temp; }
int partition(int* arr, int lower_bound, int upper_bound) { int pivot = arr[lower_bound]; int start = lower_bound; int end = upper_bound; while (start < end) { while (arr[start] <= pivot) { start++; } while (arr[end] > pivot) { end--; } if (start < end) { swap(&arr[start], &arr[end]); } } swap(&arr[lower_bound], &arr[end]); return end; }
void quick_sort(int* arr, int lower_bound, int upper_bound) { if (lower_bound < upper_bound) { int index = partition(arr, lower_bound, upper_bound); quick_sort(arr, lower_bound, index - 1); quick_sort(arr, index + 1, upper_bound); } }
int findMedian(int arr_count, int* arr) { int lower_bound = 0; int upper_bound = arr_count - 1; quick_sort(arr, lower_bound, upper_bound); return arr[arr_count/2]; }