Quicksort 3 way partition

Question

I want to implement the quicksort 3 way partition. Here is the code:

public class quick3 {

    public static void quicksort3(int a[],int l,int r) {

        int k;
        int v = a[r];

        if (r<=l)
            return;

        int i = l;
        int j = r;
        int p = l-1;
        int q = r;

        for (;;) {
            while (a[++i]<v)
                ;
            while (v<a[--j])
                if (j==i) break;

            if (i>=j)
                break;

            swap( a,i, j);

            if (a[i]==v) {
                p++;
                swap(a,p,i);
            }

            if (v==a[j]) {
                q--;
                swap( a,q,j);
            }
        }
        swap(a,i,r);
        j = i-1;
        i = i+1;
        for (k = 1; k <= p; k++, j--)
            swap(a,k,j);
        for (k = r-1; k >= q; k--, i ++)
            swap(a,k,i);
        quicksort3(a,l,j);
        quicksort3(a,i,r);
    }

    public static void main(String[]args) {
        int a[]=new int[]{4,6,5,9,7,8,3};
        quicksort3(a,0,a.length-1);
        for (int i=0;i<a.length;i++) {
            System.out.println(a[i]);
        }
    }

    public static void swap(int a[],int i,int j) {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}

After the change the result is

4
8
7
6
3
5
9

How can it be fixed?

Answer 1

Ah ha. I think you/ve been here http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

You made an error transcribing the code. It should be

int i = l - 1;

when you initialise i. This means you don't examine the leftmost element in the partition.

Also, that paper has different conditions in your for loops

for (k = 1; k < p; k++, j--)

and

for (k = r-1; k > q; k--, i++)

EDIT:

You also made a couple of other errors where you had the digit 1 where it should have been the letter l.

Finally, the two statements below were

int v = a[r];
     if (r<=l) return;

but if you do this you get an index error as the access comes before the test. Fixing these, renaming variables to something more meaningful and commenting extensively, one gets:

public class quick3 {

public static void quicksort3(int a[],int left,int right){

        int k;
    if (right<=left) return;
    int pivot_value = a[right];

    int current_left_index = left-1;
    int current_right_index = right;
    int left_equal_key_index = left-1;
    int right_equal_key_index = right;

    for (;;) {
    // skip past elements from the left with keys less than the pivot_value (i.e, already at the correct side)
    // must terminate because pivot_value is at index'right'
        while (a[++current_left_index]<pivot_value)
            ; 

        while (pivot_value<a[--current_right_index])
            if (current_right_index==left) break; // terminate if we reach the beginning. 

    // if we meet in the middle, everything is now partitioned, so bail for cleanup
    // note this is true if we broke out of the previous while.
        if (current_left_index>=current_right_index) break;

    // current_left_index points at bigger than pivot_value. 
    // current_right_index points at something smaller than pivot_value, both are in the wrong side.
    // So swap them
        swap( a,current_left_index, current_right_index);

    // if we stopped (after skipping over stuff) at something equal to pivot_value, swap it with the first element at the beginning whose value is not 'pivot_value'
    // and increment our index to the end of the elements with keys equal to pivot_value that we've stored there
        if (a[current_left_index]==pivot_value) {
            left_equal_key_index++; 
            swap(a,left_equal_key_index,current_left_index);
        }

    // and again, except move it to the end
        if (pivot_value==a[current_right_index]) {
            right_equal_key_index--;
            swap( a,right_equal_key_index,current_right_index);
        }
    }
    // after the for loop terminates...
    //the rigtmost element has value 'pivot_value'
    // all the keys of elements between left and left_equal_key_index are equal to pivot_value (there may be none of these)
    // all the keys of elements between right_equal_key_index and right are equal to pivot_value (there's at least one - the key value of the rightmost element is 'pivot_value'
    // All the keys after left_equal_key_index and before current_left_index are less than 'pivot_value'. 
    // All the keys after current_right_index and before right_equal_key_index are greater than 'pivot_value'. 

    // swap 'pivot_value' with whatever we're stlll pointing at to put it in the right place
     swap(a,current_left_index,right);

    current_right_index = current_left_index-1; // i.e. just to the left of 'pivot_value'
    current_left_index = current_left_index+1; // i.e. just to the right of 'pivot_value'
    // move all those elements with key value equal to 'pivot_value' from the beginning next to the pivot_value we just moved
    for (k = left; k < left_equal_key_index; k++, current_right_index--)
        swap(a,k,current_right_index);
    // and from the end to next to pivot_value
    // right - 1 because we already moved the pivot_value value
    for (k = right-1; k > right_equal_key_index; k--, current_left_index ++)
        swap(a,k,current_left_index);
    // now all keys equal to pivot_value are adjacent in the middle. current_left_index and current_right_index are positioned to the right (and left) 
    // respectively of those, since we don't need to sort these in recursive calls
    quicksort3(a,left,current_right_index);
    quicksort3(a,current_left_index,right);
}


   public static void main(String[]args){

    int a[]=new int[]{4,6,5,9,7,8,3};
    quicksort3(a,0,a.length-1);
    for (int l=0;l<a.length;l++){
        System.out.println(a[l]);
    }
}

public static void swap(int a[],int l,int r) {
    int t=a[l];
    a[l]=a[r];
    a[r]=t;
}

... which appears to work. I still maintain you'd have got more value from debugging it yourself.

(Although the original authors who used both 1 and l - and apparently a language that doesn't give out-of-range index errors) need chastising too)