fundamental C quicksort

user_13138659 0
Viewed 62

I'm struggling with quicksort in Knking example.

int split(int a[], int low, int high)
{
    int part_element = a[low];
    
    for(;;)
    {
        while(low < high && part_element <= a[high])
            high--;
        if(low >= high)
            break;
        a[low++] = a[high];
        
        while(low < high && a[low] <= part_element)
            low++;
        if(low >= high)
            break;
        a[high--] = a[low];
        }
    
    a[high] = part_element;
    return high;
}

I wonder why the condition if(low >= high) has >. evertime high gets smaller and low gets bigger they sometime be the same. why the book included the > in the condition? I think it is enough with if(low == high).

In which situation low can be bigger than high?

quicksort c
1 Answers

While it is true the code in split cannot cause high to become less than low, using >= is useful because:

  • The routine may be called with high already less than low. For example, if a program filters a list of some things, and ends up with zero things1 and then tries to sort the empty list using quicksort, it will call it with low = 0 and high = −1.2 When this happens, we want to split to exit without making any modifications.
  • Using >= generally has the same performance as ==; the processor does not do any extra work for >=. Commonly, int values are compared with a single instruction that completely determines the relationship (<, =, or >, sometimes with other results as well) and reports them in flags or a result register. Then another instruction branches based on the results.
  • It is good practice to guard against bugs. In case some mistake in the source code causes high to become less than low, we might prefer the routine to exit before doing any further damage. (Which decisions to make in such cases are generally sensitive to the situation.)

Footnote

1 For example, consider a real estate search engine for which a user has requested information about houses for sale in a certain town. The software might retrieve all such houses from a database. Then it might apply the user’s filters, such as eliminating all houses except those that have three bedrooms and are less than a certain price. The result of those filters might be an empty list.

2 In the original code, quicksort contains its own test that prevents it from calling split with low greater than high, so this reason does not apply with this particular calling code. Nonetheless, it is a good design for split to behave well when called with low greater than high.

user_2982250
Related