Сортировка подсчётом

Сортировка подсчётом (counting sort) — нераспределительный алгоритм сортировки, работающий за O(n + k), где k — диапазон значений; не использует сравнения, подсчитывая встречаемость каждого значения.

Зачем нужно

Counting Sort обходит нижнюю границу O(n log n) для сортировок сравнением, достигая O(n + k). Это делает её идеальной для целых чисел в ограниченном диапазоне: сортировка оценок (0–100), ASCII-символов, возрастов. Она является строительным блоком для Radix Sort.

Где используется

  • Сортировка целых чисел в небольшом диапазоне [0, k]
  • Radix Sort использует Counting Sort как субалгоритм
  • Сортировка символов строк (символы ASCII)
  • Гистограммы и частотный анализ данных

Основной контент

Алгоритм

  1. Создать массив count размером k+1, инициализировать нулями.
  2. Для каждого элемента увеличить count[element].
  3. Для стабильной версии: преобразовать count в массив позиций (prefix sum).
  4. Построить выходной массив.

Базовая реализация (нестабильная)

function countingSort(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);

  // Шаг 1: подсчёт
  for (const x of arr) count[x]++;

  // Шаг 2: восстановление отсортированного массива
  const result = ;
  for (let i = 0; i <= maxVal; i++) {
    while (count[i]-- > 0) result.push(i);
  }
  return result;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
// [1, 2, 2, 3, 3, 4, 8]

Стабильная реализация

function countingSortStable(arr, maxVal) {
  const count = new Array(maxVal + 1).fill(0);

  // Подсчёт частот
  for (const x of arr) count[x]++;

  // Prefix sum: count[i] = число элементов <= i
  for (let i = 1; i <= maxVal; i++) count[i] += count[i - 1];

  // Построение результата (обход с конца для стабильности)
  const output = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    output[--count[arr[i]]] = arr[i];
  }
  return output;
}
// Стабильна: одинаковые элементы сохраняют исходный порядок

Расширение: произвольный диапазон [min, max]

function countingSortRange(arr) {
  if (!arr.length) return ;
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min;
  const count = new Array(range + 1).fill(0);
  for (const x of arr) count[x - min]++;
  const result = ;
  for (let i = 0; i <= range; i++) {
    while (count[i]-- > 0) result.push(i + min);
  }
  return result;
}
// Работает для любых целых чисел, не только неотрицательных

Сложность

Параметр Значение
Время O(n + k)
Память O(n + k)
Стабильная Да (в версии с prefix sum)
In-place Нет

n — число элементов, k — диапазон значений.

Когда применять

k << n (k намного меньше n) → Counting Sort выгоднее O(n log n)
k ≈ n                       → Примерно одинаково
k >> n                      → O(n log n) алгоритмы предпочтительнее

Частые ошибки

  • Применять к числам с большим диапазоном (float, большие int) — O(k) памяти неприемлемо.
  • Не смещать индекс на min при отрицательных числах — выход за границы массива.
  • Использовать нестабильную версию там, где нужно сохранить порядок объектов с одинаковым ключом.
  • Применять к нецелым числам — Counting Sort работает только с целыми.

Связанные темы

Ресурсы