Sorting arrays in Java using the flag-sort

Question

Write a static method in Java :

public static void sortByFour (int[] arr)

That receives as a paramater an array full of non-negative numbers (zero or positive) and sorts the array in the following way :

• In the beginning of the array all the numbers that devide by four without a remainder will appear.
• After them all the numbers in the array that devide by 4 with a remainder of 1 will appear.
• After them all the numbers in the array that devide by 4 with a remainder of 2 will appear.
• In the end of the array all the rest numbers (those who divide by 4 with the remainder 3) will appear.

(The order of the numbers in each group doesn't matter)

The method must be the most efficient as possible using the flag-sort. The space complexity must be O(1) and the time complexity must be O(N) or less.

NOTE: Do NOT use an extra array.

I read about the flag-sort but I don't know how to write the code of it in Java. Can someone please help me?

According to what I read, it is necessary to find the start index and end index in the array of each of the buckets. Is that correct? For this it's necessary to count how many numbers in the array divide by four with a remainder of 0, 1, 2, and 3.

Hmm...

public static void sortByFour(int[] arr) {
    int count1 = 0, count2 = 0, count3 = 0, count4 = 0;
    int startB1, startB2, startB3, startB4;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] % 4 == 0)
            count1++;
        if (arr[i] % 4 == 1)
            count2++;
        if (arr[i] % 4 == 2)
            count3++;
        if (arr[i] % 4 == 3)
            count4++;
    }
    startB1 = 0;
    startB2 = startB1 + count1;
    startB3 = startB2 + count2;
    startB4 = startB3 + count3;

    for (int i = startB1; i < arr.length; i++) {
        if (arr[i] % 4 == 0) {
            swap(arr[i], arr[startB1]);
            startB1++;
        }
    }

    for (int i = startB2; i < arr.length; i++) {
        if (arr[i] % 4 == 1) {
            swap(arr[i], arr[startB2]);
            startB2++;
        }
    }

    for (int i = startB3; i < arr.length; i++) {
        if (arr[i] % 4 == 2) {
            swap(arr[i], arr[startB3]);
            startB3++;
        }
    }
}

public static void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

I am not sure it's correct though...

Answer 1

The algorithm

The sorting algorithm that you need to implement is (a rather obscure one) called the "flag sort". Here's what Wikipedia has to say about it:

An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step.

In your case:

• There are 4 buckets
• There will be 3 steps (so no, it won't be a single loop solution)
• You need O(1) auxiliary space, best as an array, for count[], etc.
• The cyclic permutation is the tricky part, but the first 2 steps is trivial
  • (here's where you can do your part and show some work by doing the first 2 steps)

References

• Wikipedia/American Flag Sort

---

Java implementation

Here's the most straightforward implementation of the algorithm that I could do; it also has some logging statement so you can follow the algorithm. You may actually want to skip this part for now and examine the ouput below.

static void sort(int... arr) {
   final int M = 4;
   final int N = arr.length;

   int[] count = new int[M];
   for (int num : arr) {
      count[num % M]++;
   } 
   int[] start = new int[M];
   for (int i = 1; i < M; i++) {
      start[i] = start[i-1] + count[i-1];
   }       
   for (int b = 0; b < M; b++) {
      while (count[b] > 0) {
         dump(arr);
         int origin = start[b];
         int from = origin;
         int num = arr[from];
         arr[from] = -1;
         do {
            System.out.printf("Picked up %d from [%d]%n", num, from);
            int to = start[num % M]++;
            count[num % M]--;
            System.out.printf("%d moves from [%d] to [%d]%n", num, from, to);
            int temp = arr[to];
            arr[to] = num;
            num = temp;
            dump(arr);
            from = to;
         } while (from != origin);
      }
   }
}

Then we can test it as follows:

static void dump(int[] arr) {
    System.out.println("Array is " + java.util.Arrays.toString(arr));
}
public static void main(String[] args) {
    sort(3, 2, 5, 0, 6, 4, 8, 7, 1, 6);
}

This prints:

Array is [3, 2, 5, 0, 6, 4, 8, 7, 1, 6]
Picked up 3 from [0]
3 moves from [0] to [8]
Array is [-1, 2, 5, 0, 6, 4, 8, 7, 3, 6]
Picked up 1 from [8]
1 moves from [8] to [3]
Array is [-1, 2, 5, 1, 6, 4, 8, 7, 3, 6]
Picked up 0 from [3]
0 moves from [3] to [0]
Array is [0, 2, 5, 1, 6, 4, 8, 7, 3, 6]
Array is [0, 2, 5, 1, 6, 4, 8, 7, 3, 6]
Picked up 2 from [1]
2 moves from [1] to [5]
Array is [0, -1, 5, 1, 6, 2, 8, 7, 3, 6]
Picked up 4 from [5]
4 moves from [5] to [1]
Array is [0, 4, 5, 1, 6, 2, 8, 7, 3, 6]
Array is [0, 4, 5, 1, 6, 2, 8, 7, 3, 6]
Picked up 5 from [2]
5 moves from [2] to [4]
Array is [0, 4, -1, 1, 5, 2, 8, 7, 3, 6]
Picked up 6 from [4]
6 moves from [4] to [6]
Array is [0, 4, -1, 1, 5, 2, 6, 7, 3, 6]
Picked up 8 from [6]
8 moves from [6] to [2]
Array is [0, 4, 8, 1, 5, 2, 6, 7, 3, 6]
Array is [0, 4, 8, 1, 5, 2, 6, 7, 3, 6]
Picked up 7 from [7]
7 moves from [7] to [9]
Array is [0, 4, 8, 1, 5, 2, 6, -1, 3, 7]
Picked up 6 from [9]
6 moves from [9] to [7]
Array is [0, 4, 8, 1, 5, 2, 6, 6, 3, 7]

It may help you understand the algorithm if you go from understanding the output (to see what the algorithm is supposed to do), and then looking at the code (to see how it's done).

Attachments

• source code and output on ideone.com