Quick Sort 3-way Partitiion

Question

I'm trying to implement the Quick sort algorithm with the 3-way partition technique, using "m1" and "m2" as indexes to delimitate the zone where the elements are equal to the pivot. Here is my code:

public class Sorting {
private static Random random = new Random();

private static int[] partition3(long[] a, int l, int r) {
    long x = a[l];
    int m1 = l;
    int m2 = l;

    for (int i = l + 1; i <= r; i++) {
        if (a[i] < x) {
            m1++;
            m2++;
            swap(a, m1, m2);

        }

        if (a[i] == x) {
            m2++;
            swap(a, i, m1);
        }
    }
    swap(a, l, m1);


    int[] m = {m1, m2};
    return m;
}

private static void swap(long[] a, int i, int j) {
    long temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

private static void randomizedQuickSort(long[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int k = random.nextInt(r - l + 1) + l;
    long t = a[l];
    a[l] = a[k];
    a[k] = t;
    int m[] = partition3(a, l, r);
    randomizedQuickSort(a, l, m[0] - 1);
    randomizedQuickSort(a, m[1] + 1, r);
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
        a[i] = scanner.nextLong();
    }
    randomizedQuickSort(a, 0, n - 1);
    for (int i = 0; i < n; i++) {
        System.out.print(a[i] + " ");
    }
}

}

Most of the times it outputs the right answer to my tests, but sometimes doesn't. Can anyone tell me what I'm doing wrong?

Answer 1

It's much more easier if "m1" and "m2" (the two delimiters of the 'equal' zone) start from opposed sides. If the element is less than the pivot, you swap with the left delimiter and if is greater than the pivot, you swap with the right one. Otherwise, if it's equal, we just move the "i" index. It would be something like this:

 private static int[] partition3(long[] a, int l, int r) {
     long x = a[l];
     int m1 = l;
     int m2 = r;

     int i = l + 1;

     while(i <= m2) {
         if (a[i] > x) {
             swap(a, i, m2);
             m2--;
         } else if (a[i] < x) {
             swap(a, m1, i);
              m1++;
             i++;
         } else {
             i++;
         }
     }

     int[] m = {m1, m2};
     return m;
 }

Answer 2

Your code fails cases when you have repeating numbers in a list. For instance, your code fails the test case:

1 2 1 3 1

It will return something different every time due to random number generation, but it won't be the correct answer. This is an issue with your partition3() function, specifically the cases within your for loop, where you decide where to increment and flip. In this case:

if (a[i] < x) {
    m1++;
    m2++;
    swap(a, m1, m2);
}

You are missing a swap that moves the i'th index to the proper place. That swap would look like so:

if (a[i] < x) {
    m1++;
    m2++;
    swap(a, m1, m2);
    swap(a, m1, i); //The missing swap.
}

In your other if-condition, you are missing two things. First of all, it should be an else-if, to avoid unintended entering of both if-conditions. Second of all, you swap at the wrong location. You should swap at m2 (the second wall), not at m1. This is because the second wall takes care of values the same as the pivot, not the first. Corrected, your second if-condition would look like so:

else if (a[i] == x) { //Note the addition of the else
    m2++;
    swap(a, i, m2); //Corrected, now swaps at m2
}

With these corrections, your code seems to work as intended.