Im trying to change the code from picking the lowest pivot toopicking the median
ID: 3611031 • Letter: I
Question
Im trying to change the code from picking the lowest pivot toopicking the median pivot by doing the Median-of-Three pivot pickingstrategy. Can somebody help me please?public static void quick_srt(int array[],int low, int n){
int swap;
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && array[lo]< mid) {
lo++;
}
while (lo<hi && array[hi]> mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] =array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo+1 : lo, n);
}
}
Explanation / Answer
Hi... template<class T> inline void qsort (Ta[], int n) { quickSort(a, 0, n-1); }template<class T> void quickSort (T a[], int low, inthigh) { if (low == high) return; if (low + MIN_LIST_SIZE >high) insertionSort (&a[low],high - low + 1); else { int mid = (low +high) / 2; if (a[mid]< a[low]) swap (a[mid], a[low]); if (a[high]< a[low]) swap (a[high], a[low]); if (a[high]< a[mid]) swap (a[high], a[mid]); T pivot =a[mid]; swap (a[mid],a[high-1]); int i = low, j =high; while (true) { while (a[++i] <pivot) {;} while (a[--j] >pivot) {;} if (i < j) swap(a[i],a[j]); else break; } swap (a[i], a[high-1]); quickSort(a, low, i-1); quickSort(a, i+1, high); } I hope it is useful to you.