Сортировка подсчетом (простой алгоритм)

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

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

Предположим, что входной массив состоит из n целых чисел в диапазоне от 0 до k ? 1, где k \in \mathbb N. Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название.

Простой алгоритм

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого j \in \{0, ..., k - 1\} в массив A последовательно записать число j C[j] раз.

<span style="color: #003366;"><code>SimpleCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;
<!--more--></code></span>
<pre><span style="color: #0000ff;">void CountingSort (int *a, int n, int min, int max)
{
  int i, j, c;
  int *b;
  assert(n &gt; 0);
  assert(min &lt;= max);
  b = (int *)calloc(max - min + 1, sizeof(int));
  assert(b != NULL);
  for (i = 0; i &lt;= n - 1; ++i) ++b[a[i] - min];
  for (j = min; j &lt;= max; ++j)
  {
    c = b[j - min];
    while (c &gt; 0)
    {
      *a = j; ++a; --c;
    }
  }
  free(b);
}</span>


Оставить комментарий

Вы должны быть зарегистрированы чтобы комментировать.