Why does the partition function in QuickSort work even when the inner while loop seems to cause an infinite loop?

Question

I'm implementing the partition function for QuickSort, and I've come across behavior that seems confusing. Specifically, in the partition logic:

int partition(int A[], int low, 
int high)
{
   int pivot = A[low];
   int i = low + 1;
   int j = high;
   int temp;

do
{
    while (A[i] <= pivot)
    {
        i++;
    }

    while (A[j] > pivot)
    {
        j--;
    }

    if (i < j)
    {
        temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
} while (i < j);

// Swap A[low] and A[j]
temp = A[low];
A[low] = A[j];
A[j] = temp;
return j;

}

Here’s my concern:

When iterating through the while (A[i] <= pivot) loop, if all the elements on the left side are smaller than or equal to the pivot, i keeps incrementing until it exceeds the bounds (high).

Similarly, the while (A[j] > pivot) loop causes j to decrement when elements on the right are larger than the pivot.

If i or j cross boundaries (e.g., i > high), shouldn’t this cause the do-while loop to break unexpectedly or even enter an infinite loop?

For example, if the input array is {12, 6, 7, 9, 10}, and the pivot is 12, the i pointer would increment up to 5 (out of bounds) since all elements are less than or equal to the pivot. However, this code still works and produces a correct partition.

Question: Why does this code still work, even though i seems to exceed the bounds during the while (A[i] <= pivot) loop? How is the infinite loop avoided in this case?

You could use a debugger to step through the code line by line while monitoring variables and their values, to see what really happens. I recommend using pen and paper to write down all details. — Some programmer dude
– Some programmer dude, Commented Jan 25 at 11:26

rcgldr · Accepted Answer · 2025-01-26 06:51:11Z

The question's code does appear to have a potential problem with the first loop (setting i to low+1 and looping for a[i++] until > pivot) To avoid bounds checking, i needs to be set at or before the pivot, and the compare needs to be < not <=. Example code for a post-incrementing | post-decrementing variation of Hoare partition. If an element equal to the pivot or the pivot itself is encountered, that element will get swapped, and prevent the next instance of the two inner loops from going going out of bounds.

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}

Collectives™ on Stack Overflow

Why does the partition function in QuickSort work even when the inner while loop seems to cause an infinite loop?

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related