How to implement medianOf3 in quicksort algorithm

Question

I'm trying to implement this medianOf3 method with the quicksort algorithm; however, nothing I've done is working. I know my quicksort method is working however my method for partitioning is failing to partition correctly if anyone has any suggestions for implementing this medianOf3 method to with my quicksort algorithm it would be greatly that would be immensely helpful. In addition I did include <bits/stdc++.h>, , , and include . I added using std::swap; and using namespace std; as well.

template<typename T> inline
int medianOf3(T A[], int l, int r){
        //this is overcommented... also, try and avoid using pointers
        T* a = A + l;//array name is just pointer to 1st (0 index) elem., + l shifts l*(T size)
        T* b = A + l + (r-l)/2;//middle item... int division rounds down
        T* c = A + r;

        //when a is a pointer, *a is the dereference operator (gives value a points to)
        T* m;
        if(*a < *b){
                if(*b < *c) m=b;
                else if(*c < *a) m=a;
                else m=c;
        } else{ //b <=a8
                if(*a < *c) m=a;
                else if(*c < *b) m=b;
                else m=c;
        }
        return m-A; //m-A is the number of elements from A[0]

}
int partition(int a[], int l, int r){
    int s = medianOf3(a, l, r);
    swap(a[l], s);
    int p = a[l];
    int i = l; 
    int j = r;
    while(i<j){
        do{
            i=i+1;
        }while(a[i]<=p);
        do{
            j=j-1;
        }while(a[j]>p);
        if (i<j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    return j;
}
void quickSort(int arr[], int l, int r){
    if (l < r){
        int p = partition(arr, l, r);
        quickSort(arr, l, p - 1);
        quickSort(arr, p + 1, r);
    }
}

Answer 1

partition() is an attempt to implement Hoare partition scheme, but there are some issues. Here is a working example:

int medianof3(int a[], int lo, int hi)
{
    int md = lo+(hi-lo)/2;              // median of 3
    if(a[lo] > a[hi])
        std::swap(a[lo], a[hi]);
    if(a[lo] > a[md])
        std::swap(a[lo], a[md]);
    if(a[md] > a[hi])
        std::swap(a[md], a[hi]);
    return md;
}

int partition(int a[], int lo, int hi)
{
    int md = medianof3(a, lo, hi);      // median of 3
    int p = a[md];                      // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    return j;                           // return index to split point
}

void quicksort(int a[], int lo, int hi)
{
    if(lo >= hi)                        // return if nothing to do
        return;
    int s = partition(a, lo, hi);       // partition
    quicksort(a, lo, s);                // recurse
    quicksort(a, s+1, hi);
}

---

All of this can be included in the quicksort function

void quicksort(int a[], int lo, int hi)
{
    if(lo >= hi)                        // return if nothing to do
        return;
    int md = lo+(hi-lo)/2;              // median of 3
    if(a[lo] > a[hi])
        std::swap(a[lo], a[hi]);
    if(a[lo] > a[md])
        std::swap(a[lo], a[md]);
    if(a[md] > a[hi])
        std::swap(a[md], a[hi]);
    int p = a[md];                      // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    quicksort(a, lo, j);                // recurse
    quicksort(a, j+1, hi);
}