CODEWITHSUNDEEP
javaalgorithmsortingquicksortpseudocode
Stacky
Stacky

Reputation: 488

Quick sort 3 way - why loop index is not incremented when element is greater than pivot?

I have been searching for this in many questions related to 3 way quicksort but could not find an answer/explanation (like this and similar - Quicksort with 3-way partition).

Below is the 3-ways quick sort code from Robert Sedgewick and Kevin Wayne book "Algorithms".

private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }

    sort(a, lo, lt-1);
    sort(a, gt+1, hi);
}

After partitioning, elements left to the pivot should be lesser than the pivot and those on right greater than the pivot. Elements equal to pivot should be together in the middle. I have tried writing the above code each step-wise in detail but am unable to understand why i is not incremented when the element is greater than the pivot. It is incremented when the element is less than the pivot:

else if (cmp > 0) exch(a, **i, gt--**);

It would be great if someone could explain this partitioning scheme.

Upvotes: 0

Views: 285

Answers (1)

MBo
MBo

Reputation: 80187

Because you should check a[i] element (former a[gt]) again - it is unknown yet - whether that element is small or big

*  *  *  *  *  *  *  *
      ^     ^     ^
      lt    i     gt

Look at some intermediate situation: i is not smaller than lt and is not larger than gt.

Elements being left to i have been already checked to be not larger than pivot.

If we exchange a[i] with a[lt], we know that a[i] is small and must go on, incrementing i.

If we exchange a[i] with a[gt], we don't new value of a[i] and must check it again

P.S. Note that linked question is about 3-way partition with two pivot values, while Sedgewick algo is for 'dutch flag' partition with one pivot and special treatment for values equal to pivot

Upvotes: 1

Related Questions