Сортировка массивов в Java с использованием flag-sort

Question

Напишите статический метод в Java:

public static void sortByFour (int[] arr)

Получает в качестве параметра значение, полное неотрицательных чисел (ноль или положительное число), и сортирует массив следующим образом:

• В начале массива появятся все числа, которые делятся на четыре без остатка.
• После них появятся все числа в массиве, которые делятся на 4 с остатком 1.
• После них появятся все числа в массиве, которые делятся на 4 с остатком 2.
• В конце массива все остальные числа (те, которые делят на 4 споявится остаток 3).

(Порядок чисел в каждой группе не имеет значения)

Метод должен быть максимально эффективным при использовании сортировки по флагу.Сложность пространства должна составлять O (1) , а сложность времени должна составлять O (N) или менее.

ПРИМЕЧАНИЕ: НЕиспользуйте дополнительный массив.

Я читал о сортировке флагов, но не знаю, как написать ее код на Java.Может кто-нибудь помочь мне?

Согласно тому, что я прочитал, необходимо найти начальный и конечный индексы в массиве каждого из сегментов.Это верно?Для этого необходимо посчитать, сколько чисел в массиве разделить на четыре с остатком 0, 1, 2 и 3.

Хмм ...

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

Я неконечно, это правильно, хотя ...

Answer 1

Алгоритм

Алгоритм сортировки, который вам нужно реализовать, (довольно неясный) называется «сортировкой по флагу». Вот что говорит об этом Википедия:

Эффективный вариант сортировки по основанию, который распределяет элементы по сотням корзин. Первый шаг подсчитывает количество элементов в каждой корзине, а второй шаг вычисляет, где каждая корзина будет начинаться в массиве. Последний шаг циклически переставляет элементы в правильное ведро. Поскольку сегменты в массиве расположены по порядку, шаг сбора отсутствует.

В вашем случае:

• Есть 4 ведра
• Там будет 3 шага (так что нет, это не будет одноконтурным решением)
• Вам нужно O(1) вспомогательное пространство, лучше всего как массив, для count[] и т. Д.
• Циклическая перестановка - сложная часть, но первые 2 шага тривиальны
  • (здесь вы можете внести свой вклад и показать некоторую работу, выполнив первые 2 шага)

Ссылки

• Википедия / сортировка по американскому флагу

---

Реализация 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