Sorting arrays in Java using flag sorting

Question

Write a static method in Java:

public static void sortByFour (int[] arr)

It receives as an argument an array full of non-negative numbers (zero or positive), and sorts the array as follows:

• At the beginning of the array will appear all numbers that are divided into four without a remainder.
• After them, all numbers in the array will appear, which are divided by 4 with the remainder of 1.
• After them, all numbers in the array will appear, which are divided by 4 with the remainder of 2.
• At the end of the array, all other numbers will appear (those that are divisible by 4 with the remainder of 3).

(the order of numbers in each group does not matter)

The method should be as efficient as possible using flag sorting. The complexity of the space should be O (1) , and the time complexity should be O (N) or less.

NOTE. DO NOT use an extra array.

I read about flag sorting, but I don't know how to write this code in Java. Can someone please help me?

According to what I read, you need to find the index of the beginning and end of the index in the array of each of the buckets. It's right? To do this, you need to calculate how many numbers in the array divide by four with the remainder of 0, 1, 2, and 3.

Hm ...

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'm not sure if this is true, though ...

Answer 1

Algorithm

The sorting algorithm you need to implement (rather obscure) is called "flag sorting". Here is what Wikipedia has to say about it:

, radix, . , , . . , .

:

• 4
• 3 ( , )
• O(1) , , count[] ..
• - , 2
  • (, - , 2 )

• Wikipedia/American Flag Sort

---

Java

, ; , . .

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);
      }
   }
}

:

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);
}

:

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]

, , ( , ), ( , ).

• ideone.com