cquicksorthoare-logic

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


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"


Solution

  • 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.