QuickSort Infinite Loop in C?

Question

I face infinite loop issue in my quick sort algorithm, this thing happen in right sub array partition, so if I only partition the left sub array it works great like this code.

#include <stdio.h>
int list[] = {8, 1, 3, 4, 2, 10, 4, 6};
//int list[] = {2, 1, 10, 4, 5, 11, 12, 6};
//int list[] = {1, 2, 4,  5, 6, 11, 12, 10};
int main(int argc, char **argv)
{

    printf("Unsorted list is: ");
    printArray(list);
    quickSort(list, 0, 7);
    //partition(list, 5, 7);
    printf("Sorted list is: ");
    printArray(list);

    return 0;
}

void printArray(int list[]){
    int i;
    for(i = 0; i < 8; i++){
        printf(" %d ", list[i]);
    }   
    printf("\n\n");
}

void quickSort(int list[], int low, int high){

    int pIndex = partition(list, low, high);

    if(pIndex <= 0){
        return;
    }

    //quick sort left sub array
    quickSort(list, low, pIndex-1);

    //quick sort right sub array
//  quickSort(list, pIndex+1, high);

    printf("pIndex is %d\n", pIndex);
}

int partition(int list[], int low, int high){
    int pivot = list[high];


    int i;
    int j = high - 1;
//  int j = high;


    while( 1 ){
        //less than pivot
        for(i = 0; list[i] < pivot; i++){
            printf("for %d (index %dth) < %d\n", list[i], i, pivot);
            //do nothing
        }
        printf("less than stop at index %d which is %d\n", i, list[i]);

        //more than pivot
        for(j = j; j > 0 && pivot < list[j]; j--){
            printf("for %d < %d (index %dth)\n", pivot, list[j], j);
        }
        printf("greater than stop at index %d which is %d\n", j, list[j]);

        if(i >= j){
        printf("low index %d >= %d then swap pivot\n", i, j);
        printf("swap index %dth which is %d, with index pivot %d which is %d\n", i, list[i], high, list[high]);
        swap(list, i, high);

        printf("Temporary list is: ");
        printArray(list);

        printf("then return last position index pivot %d which is %d\n", i, list[i]);
        return i;
        break;
        }

        //tukarPosisi, sehingga yang kecil di sebelah kiri, yang besar di sebelah kanan.
        printf("swap index %dth which is %d, with index %dth, which is %d\n", i, list[i], j, list[j]);
        swap(list, i, j);

        printf("Temporary list is: ");
        printArray(list);


    }
}

void swap(int list[], int i, int j){
    //variabel sementara untuk menampung i
    int temporary = list[i];

    //tukar posisi, sehingga yg kecil di kiri, yg besar di kanan.
    list[i] = list[j];
    list[j] = temporary;
}

I have already print much debug but still can't figure out why this thing happen. So where is the logic wrong and how to fix it?

Any help will be appreciated

You might want to start by creating function prototypes of the functions you call, before you call them. Turn on more warnings by the compiler. And use a debugger to step through the code.' — Some programmer dude, Oct 05 '16 at 17:13
Your `partition` function appears broken: it acts as if the subarray being partitioned always starts at index `0`, regardless of the value of its `low` parameter. — John Bollinger, Oct 05 '16 at 17:20
That's not standard C and your compiler should warn. Don't even think about learning K&R-C! — too honest for this site, Oct 05 '16 at 17:30
@JohnBollinger yes always choose the most right element is bad practice, but I doesn't matter so far for me as I am learning how QuickSort works and understand it. — Dark Cyber, Oct 05 '16 at 17:31

score 0 · Answer 1 · answered Oct 05 '16 at 18:00

You have several problems with your code, mostly affecting its efficiency rather than its correctness. Several of those were called out in comments. The biggest problem, however, is the termination condition for your recursion, as you might expect given the nature of the incorrect behavior.

Specifically, your recursion bottoms out when partition() returns a value less than or equal to zero, but that function always returns the final position chosen for the pivot. If you recurse down the left side of your partitions only, then you are certain of getting that zero eventually, but when you recurse down any partition that doesn't include element 0, partition() will never return 0.

You should instead break from the recursion based on the size of the segment to be sorted (i.e. high - low). If it is less than 1 then you can stop, because a segment with fewer than two elements is certain to be already in sorted order.

QuickSort Infinite Loop in C?

1 Answers1