Encountering an infinite loop in quicksort(hoare), but I don't seem to find the issue

Question

So, I wrote a quicksort algorythm and a hoare-partition algorythm. Somehow when I try to run the example case in main (), it hangs up on quickSort(test, 0,3). There seems to be an infinite loop. I don't see how to fix it, since the two functions individually seem to be fine.

I tried debugging, but I am fairly new to c. I noticed that quickSort(test,0,3) calls itself recursively. So I know the issue has something to do with high not decreasing. But I took example pseudo code from an university slide to built the function and everything seems to line up.

void printArray(int A[], int high) {
    for (int i=0; i<=high; i++) {
         printf("%d ", A[i]);
    }
}

int partitionHoare(int A[], int low, int high) {
    int pivot=A[low];
    int left = low-1;
    int right= high+1;

    while (1){
        while (1){
            left++;
            if (A[left]>=pivot) break;
        }
        while (1){
            right--;
            if (A[right]<=pivot) break;
        }


        if (left<right)  {
            int temp=A[left];
            A[left]=A[right];
            A[right]=temp;
        }
        else return left;
    }
}

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}


void main (){
    int test[]={64,81,24,42,90,30,9,95};
    quicksort(test,0,7);
    printArray(test,7);

I actually expect the test array to be printed out sorted like this: "9, 24, 30, 42, 64, 81, 90, 95"

Answer 1

Change partition to return right (instead of left). Change the two recursive calls to | quicksort(A, low,middle); | quicksort(A, middle+1, high);. This will exactly match the wiki article's example:

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

You may want to change the name of "middle". Wiki example calls it p meaning partition split index (as opposed to meaning index to pivot), since with Hoare partition scheme, the pivot and elements equal to the pivot may end up at the end of the left partition and/or at the start of the right partition.

Answer 2

You have a logical deficiency in your quicksort() function:

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}

It does not ensure that the recursion will terminate.

Specifically, if, in some sub-array of length greater than 1, the first element is the least and is not a duplicate then partitionHoare() will return a value equal to low without modifying the array. In that case, the recursive call for the left subarray will do nothing, but the recursive call for the right subarray will reiterate the current arguments exactly. Nothing having changed, the same thing is then guaranteed to happen again, and again, indefinitely.

You could break the infinite recursion in that case by testing in quicksort() whether middle == low, but that doesn't give you a correct sort.

One common solution here is twofold:

1. Ensure that the partition function swaps the pivot value to the pivot index it reports. This is certain to be a correct final position for that value.
2. When recursing, exclude the pivot index (whose value we know is correct) from both sub-arrays, so that each sub-problem is certain to be smaller than the parent problem.