How do i implement Quicksort correctly?

Question

I'm trying to implement quicksort and I am following steps in my book and I don't understand how the median of three should be implemented. I followed book instructions but I don't understand why the median of three actually helps with? I never actually do anything with it.

Here is my implementation:

Herer is my Quicksort implementation.

void QuickSort::QuickSortM3(std::vector<int> &data, int left, int right){    
    if(left < right){
        pivotM3(data, left, right);
        int i = partition(data, left, right);

        QuickSortM3(data, left, i-1);
        QuickSortM3(data, i +1, right);
    }

}

void QuickSort::pivotM3(std::vector<int> &data,  int left, int right){
    std::swap(data[(left+ right)/2], data[(right -1)]);
    if(data[left] < data[right-1]){
        std::swap(data[left], data[right-1]);
    }
    if(data[left] < data[right]){
        std::swap(data[left], data[right]);
    }
    if(data[right -1] < data[right]){
        std::swap(data[left], data[right-1]);
    }

}

int QuickSort::partition(std::vector<int> &data,  int left, int right){
    int i = left - 1, j = right; int v = data[right];

    for(;;){

        while(data[++i] < v);
        while (v < data[--j]){
            if( j == left) {
            break;
            }
        } 
        if(i >= j) break;
        std::swap(data[i], data[j]);        
    }
    std::swap(data[i], data[right]);
    return i;
}

What I actually mean is, should I not be using the middle element in the partitioning? Any help would be great, thank you.

What do you mean, "median of three"? Is that some term from your book? I haven't read your book. — Cubic, Apr 22 '19 at 17:00
"How do i implement Quicksort correctly?" - call `std::sort` — Jesper Juhl, Apr 22 '19 at 17:07
This post should clarify. https://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot — Logan Cooper, Apr 22 '19 at 17:11
@JesperJuhl this would not be correct, as `std::sort` doesn't implement quick sort. — SergeyA, Apr 22 '19 at 17:34
@SergeyA fair enough. But it still meets the end goal of sorting the container. — Jesper Juhl, Apr 22 '19 at 17:40
@Cubic No, Median of three is not only a term from my book. It is a kind of quicksort where you choose, the first, middle and last element and swap them around. — Ninhow, Apr 22 '19 at 17:47
[median of three values strategy](https://stackoverflow.com/questions/7559608/median-of-three-values-strategy) — crashmstr, Apr 22 '19 at 19:32

rcgldr · Accepted Answer · 2019-04-23T05:30:54.720

Example of Hoare partition scheme using median of 3:

void QuickSort(int a[], int lo, int hi)
{
    if(lo >= hi)
        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 v = a[md];              // partition
    int i = lo - 1;
    int j = hi + 1;
    while(1)
    {
        while(a[++i] < v);
        while(a[--j] > v);
        if(i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    QuickSort(a, lo, j);
    QuickSort(a, j+1, hi);
}

How do i implement Quicksort correctly?

1 Answers1