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

Question

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.

MBo · Accepted Answer · 2016-12-02 02:07:42Z

1

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

edited Dec 2, 2016 at 2:07

answered Dec 2, 2016 at 1:41

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Stacky Over a year ago

Thanks but to fully understand this (and sorry haven't been able to): Why is it incremented in less than case? exch(a, lt++, i++);

Stacky Over a year ago

"If we exchange a[i] with a[lt], we know that a[i] is small and must go on, incrementing i." - ok, a[i] is smaller than pivot and must go on. "If we exchange a[i] with a[gt], we don't new value of a[i] and must check it again" - isn't a[i] i.e. older a[gt] > pivot and i.e. why it is being exchanged?

Stacky Over a year ago

Ok, a[i] > pivot and not a[gt], it is just exchanged to move the greater element at the end and we do not know about the element with which it was swapped though. Correct?

MBo Over a year ago

Yes, absolutely

MBo Over a year ago

There is useful concept of 'loop invariants' - you thoroughly check state of data before and after every algorithm cycle run and watch that some needed state (partial ordering etc) is still keeping (and gets better).Though sometimes it is not easy to select these invariants. Seems that in this concrete case you just missed data flow peculiarity - that unknown element replaces treated one.

|

Collectives™ on Stack Overflow

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

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related