Подсчет сортировки - различия в реализации

Question

Я слышал о Counting Sort и написал свою версию на основе того, что я понял.

public void my_counting_sort(int[] arr)
    {
        int range = 100;
        int[] count = new int[range];
        for (int i = 0; i < arr.Length; i++) count[arr[i]]++;
        int index = 0;
        for (int i = 0; i < count.Length; i++)
        {
            while (count[i] != 0)
            {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

Приведенный выше код работает отлично.

Однако алгоритм, приведенный в CLRS, отличается,Ниже моя реализация

public int[] counting_sort(int[] arr)
    {
        int k = 100;
        int[] count = new int[k + 1];
        for (int i = 0; i < arr.Length; i++)
            count[arr[i]]++;
        for (int i = 1; i <= k; i++)
            count[i] = count[i] + count[i - 1];
        int[] b = new int[arr.Length];
        for (int i = arr.Length - 1; i >= 0; i--)
        {
            b[count[arr[i]]] = arr[i];
            count[arr[i]]--;
        }
        return b;
    }

Я непосредственно перевел это из псевдокода в C #.Код не работает, и я получаю исключение IndexOutOfRange.

Итак, мои вопросы:

• Что не так со вторым фрагментом кода?
• Что такоеРазумный алгоритм мудрости между моей наивной реализацией и той, что приведена в книге?

Answer 1

Проблема с вашей версией в том, что она не будет работать, если у элементов есть спутниковые данные.

Версия CLRS будет работать и будет стабильной.

РЕДАКТИРОВАТЬ:

Вот реализация версии CLRS в Python, которая сортирует пары (ключ, значение) по ключу:

def sort(a):
  B = 101
  count = [0] * B
  for (k, v) in a:
    count[k] += 1
  for i in range(1, B):
    count[i] += count[i-1]
  b = [None] * len(a)
  for i in range(len(a) - 1, -1, -1):
    (k, v) = a[i]
    count[k] -= 1
    b[count[k]] = a[i]
  return b    


>>> print sort([(3,'b'),(2,'a'),(3,'l'),(1,'s'),(1,'t'),(3,'e')])
[(1, 's'), (1, 't'), (2, 'a'), (3, 'b'), (3, 'l'), (3, 'e')]

Answer 2

Это должно быть

b[count[arr[i]]-1] = arr[i];

Я оставлю это вам, чтобы выяснить, почему; -).

Я не думаю, что они работают по-другому.Второй просто выталкивает корреляцию отсчетов из цикла, так что он немного упрощается в последнем цикле.Это не обязательно, насколько я понимаю.Ваш путь так же прост и, вероятно, более читабелен.На самом деле (я не знаю о C #, так как я парень по Java), я ожидаю, что вы можете заменить этот внутренний цикл while заполнением массива библиотеки;как-то так:

       for (int i = 0; i < count.Length; i++)
    {
        arrayFill(arr, index, count[i], i);
        index += count[i];
    }

В Java метод java.util.Arrays.fill(...).

Answer 3

Проблема в том, что вы жестко запрограммировали длину используемого вами массива в 100. Длина массива должна быть m + 1, где m - максимальный элемент в исходном массиве. Это первая причина, по которой вы могли бы подумать, используя counting-sort, если у вас есть информация об элементах массива, которые незначительны, чем некоторые константы, и это будет работать отлично.