CODEWITHSUNDEEP
c++algorithmquicksortpartitioninghoare-logic
Joe Black
Joe Black

Reputation: 653

Hoare partitioning code used in Quicksort (ref Cormen book) runs into infinite loop

I code Quicksort using Hoare partitioning from the Cormen Algorithms book. I can't spot any mistakes in my code and it looks just like the pseudocode in the book. 

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

swapping i, j : 0, 1
-3 -2 -5 2 6 0 1 0 -1 4
p is: 0

After it has done the above swaps, this code eventually ends up partitioning on a subarray {-3, -2}. For this subarray, pivot is -3 and the partition() returns 0 as the index (j). Since this subarray is already sorted with pivot -3 at 0th index position, no changes are done every time this is quicksorted. So the qsort loops forever.

Can someone tell me how this is different from the Hoare partition in the book and if same why is this not working?

void swap(int *a, int i, int j) {
        cout << "swapping i, j : " << i << ", " << j << endl;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp; }

int partition(int *a, int len) {
        int pivot = a[0];

        int i = -1, j = len;
        while (true) {
               while ( ++i && a[i] < pivot && i< j) {}
               while (--j && a[j] > pivot && i <j) {}
               if (i < j )
                  swap(a, i, j);
               else 
                  return j ;
        } }

void qsort(int a[], int len) {
        int p = partition(a, len);
        cout << "p is: " << p << endl;
        qsort(a, p);
        qsort(a+p, len - p ); }

int main(int argc, char *argv[]) {
        int a[10] = {-1, 2, -5, -3, 6, 0, 1, 0, -2, 4};
        qsort(a, 10); }

Upvotes: 0

Views: 397

Answers (1)

CinCout
CinCout

Reputation: 9619

Extending my comment in an answer, partition() returns 0-based index, but you need to pass the array length (length is 1-based) to qsort(), so it must be:

void qsort(int a[], int len)
{
    int p = partition(a, len);
    cout << "p is: " << p << endl;
    qsort(a, p + 1); // note p+1 instead of p
    qsort(a + p + 1, len - (p + 1)); // note p+1 instead of p
}

The dry run will look like:

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

Now you must call qsort(a, 3) since you want to sort the sub-array -2 -3 -5. Also, qsort(a+3, 7) for the sub-array 2 6 0 1 0 -1 4

Upvotes: 1

Related Questions