CODEWITHSUNDEEP
c++quicksortpartitioning
Toma Radu-Petrescu
Toma Radu-Petrescu

Reputation: 2262

Hoare partition doesn't work?

I have been trying to implement the Hoare partitioning method, but neither I, nor the computer can't seem to understand it as it is written in Cormen and Wikipedia. The algorithm in both sources looks like this:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            j := j - 1
        while A[j] > pivot
        do
            i := i + 1
        while A[i] < pivot
        if i < j then
            swap A[i] with A[j]
        else
            return j

For the following array: 9 3 11 55 4 , after partitioning it with the above function, it will look like this: 4 3 11 55 9 and the pivot index will be 2 which is completely false. Firstly, 9 and 4 will be swapped, so i will become 2 and j will become 4. But, during the next iteration, because of the do while loop, 9 will be skipped and will never ever be swapped again. Is there a problem with my thinking? (I think that my implementation in C++ doesn't have any mistakes)

#include <iostream>
using namespace std;
int a[100];
int partitie(int st, int dr){
    int i,j,x;
    x=a[st];
    i=st-1;
    j=dr+1;
    while(true){
        do{
            j--;
        }while(a[j]>x);
        do{
            i++;
        }while(a[i]<x);
        if(i<j) swap(a[i],a[j]);
        else return j;
    }
}
int main() {
    int i,n;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cout<<partitie(1,n)<<endl;
    for(i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

Upvotes: 0

Views: 1324

Answers (1)

rcgldr
rcgldr

Reputation: 28826

You need to use the correct quicksort routine, since Hoare splits an array into left part and right part, unlike Lomuto which splits an array into left part, pivot, right part.

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)        // not quicksort(A, lo, p-1)
        quicksort(A, p + 1, hi)

also choosing a pivot in the middle means that an already sorted or reverse sorted array is sorted quickly as opposed to being worst case:

    pivot := A[lo+(hi-lo)/2]  // or := A[(lo+hi)/2] if overflow not an issue

There would still be worst case patterns, but at least the simple ones are handled. Median of 3 is a bit slower, but reduces the number of worst case patterns:

    md = lo + (hi-lo)/2
    if (A[lo] > A[hi])
        swap(A[lo], A[hi])
    if (A[lo] > A[md])
        swap(A[lo], A[md])
    if (A[md] > A[hi])
        swap(A[md], A[hi])
    pivot := a[md]

Perhaps what you're looking for is quick select to find the kth element where k = array size / 2. It's similar to quick sort, but it only recursively searches the left or right part of the array that contains the kth element. Wiki article:

http://en.wikipedia.org/wiki/Quickselect

Upvotes: 1

Related Questions