My QuickSort code sometimes run but sometimes it does not and I don't know where error got happened

Question

int partition(int list[], int left, int right) {
    int low = left + 1;
    int high = right;
    int pivot = list[left];

    while (low < high) {
        while (low <= right && list[low] < pivot) {
            low++;
        }
        while (high >= left && list[high] > pivot) {
            high--;
        }
        if (low < high) Swap(&list[low], &list[high]);
    }
    Swap(&list[high], &list[left]);
    return high;
}

void quicksort(int list[], int left, int right) {
    if (left <= right) {
        int p = partition(list, left, right);
        quicksort(list, left, p - 1);
        quicksort(list, p + 1, right);
    }
}

This code is sometimes successfully well sorted but sometimes it cannot make any consequences and run unstoppably. which part should I fix it?

Answer 1

The problem is when the the function partition encounters an array with only two elements. In that case if the first element is smaller than the second element, the last swap call will shuffle the array.

You need to check if the swap is sensible:

if( list[high] < list[left] )
{
    Swap( &list[high] , &list[left] );
}

Also you need to increment and decrement variables low and high after you swap them in the innermost loop:

if (low < high) 
{
    Swap(&list[low], &list[high]);
    low++;
    high--;
}

And high should probably stop at left+1, and not at left here:

 while (high >= left &&