0

Here's the original question

Give you an array which has n integers,it has both positive and negative integers.Now you need sort this array in a special way.After that,the negative integers should in the front,and the positive integers should in the back.Also the relative position should not be changed. eg. -1 1 3 -2 2 ans: -1 -2 1 3 2.

My Java code (translated from Wikipedia's pseudocode)

package ThreewayPartition;

import java.util.Arrays;

public class ThreewayPartition {
    public void sort(int[] input, int mid) {
        int i=0;
        int j=0;
        int n = input.length - 1;

        while (j <= n) {
            if (input[j] < mid) {
                swap(input, i, j);
                i++;
                j++;
            } else if (input[j] > mid) {
                swap(input, j, n);
                n--;
            } else {
                j++;
            }
        }
    }

    private void swap(int[] arr, int j, int k) {
        int tmp = arr[j];
        arr[j] = arr[k];
        arr[k] = tmp;
    }

    public static void main(String[] args) {
        int[] input = {-1, 1, 3, -2, 2};
        ThreewayPartition twp = new ThreewayPartition();
        twp.sort(input, 0);
        System.out.println(Arrays.toString(input));
    }
}

I get this output: [-1, -2, 3, 2, 1] instead of [-1, -2, 1, 3, 2]

Null
  • 384
  • 2
  • 14

3 Answers3

0
Your swap() method is swapping elements, not shifting.

You can modify the sort method as shown below -

public void sort(int[] input, int mid) {
    int n = input.length - 1;
    int i=0;
    int tmpvar;
    while (n >= i) {
        if(input[n] < mid) {
            tmpvar = input[n];
            System.arraycopy(input, 0, input, 1, n);
            input[0] = tmpvar;
            i++;
        } else {
            n--;
        }
    }
}
Kartic
  • 2,935
  • 5
  • 22
  • 43
0

Probably there is nothing wrong with implementation - just Dutch national flag inplace partition is not stable.

Brayoni
  • 696
  • 7
  • 14
MBo
  • 77,366
  • 5
  • 53
  • 86
  • What do you mean by - _just Dutch national flag in-place partition is not stable_? – Brayoni Apr 28 '20 at 08:17
  • @Brayoni Some sort algorithms are ["stable"](https://en.wikipedia.org/wiki/Category:Stable_sorts) - they do not change mutual positions of equal elements. Here 1, 3, 2 are essentially equal (against comparing with zero - they are positive) but sorting perturbates them – MBo Apr 28 '20 at 08:42
  • Cool, thank you. I have now learnt about [stability](https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important). I was just confused about how that relates to the question. Dinesh had [a bug](https://stackoverflow.com/a/61475610/7695722) in his sort algorithm. – Brayoni Apr 28 '20 at 08:43
  • 1
    @Brayoni And after the correction Dutch national flag sorting fulfills this requirement: `Also the relative position should not be changed`? – MBo Apr 28 '20 at 08:47
  • I had missed that, thank you for pointing it out. I will add a note to my answer to that effect. – Brayoni Apr 28 '20 at 09:03
0

I had a look at Wikipedia's pseudocode and I noticed that mid is used incorrectly in sort(). It should be used as a value, i.e, input[mid].

That being said Dutch National Flag algorithm is not stable and will not satisfy the constraint in the question:

the relative position should not be changed

However, it's important to mention that the problem is a variant of the DNF algorithm.

So you are looking for something along the following lines:

import java.util.Arrays;

public class ThreewayPartition{

    public static void sort(int[] A, int mid) {
        int startIndex = 0;

        for (int i = 0; i < A.length; i++) {
            if (A[i] <= mid) {
                int temp = A[i];
                for (int j = i; j > startIndex; j--) {
                    A[j] = A[j-1];
                }
                A[startIndex] = temp;

                if (temp < mid) startIndex++;
            }
        }
    }

    public static void main(String[] args) {
        int[] input = {-1, 1, 3, -2, 2};
        ThreewayPartition twp = new ThreewayPartition();
        twp.sort(input, 0);
        System.out.println(Arrays.toString(input));  // [-1, -2, 1, 3, 2]
    }
}

Please note that the code's time complexity is O(n*n).

A more efficient, time complexity O(n), and simpler to understand:

import java.util.Arrays;

public class ThreewayPartition{

    public static void sort(int[] A, int mid) {

        for (int i = A.length - 1; i > 0; i--) {
            if (A[i] <= mid && A[i - 1] > mid) {
                swap(A, i, i-1);
            }
        }
    }

    private static void swap(int[] arr, int j, int k) {
        int tmp = arr[j];
        arr[j] = arr[k];
        arr[k] = tmp;
    }

    public static void main(String[] args) {
        int[] input = {-1, 1, 3, -2, 2};
        ThreewayPartition twp = new ThreewayPartition();
        twp.sort(input, 0);
        System.out.println(Arrays.toString(input));  // [-1, -2, 1, 3, 2]
    }
}
Brayoni
  • 696
  • 7
  • 14