Counting Sort (Сортировка подсчётом)

Краткое описание

Не основана на сравнениях. Подсчитывает, сколько раз встречается каждое значение, затем восстанавливает отсортированный массив по этим счётчикам. Работает за линейное время O(n + k), где k — размер диапазона значений. Идеальна для целых чисел в небольшом известном диапазоне.

Когда использовать

• Целые числа (или то, что сводится к целым ключам) в известном и небольшом диапазоне, где k ≈ n
• Нужна стабильная сортировка за линейное время
• Как подпрограмма внутри Radix Sort (стабильная сортировка по одному разряду)

Когда не стоит использовать:

• Большой диапазон значений (k ≫ n) — память и время O(k) становятся неприемлемыми
• Дробные числа, строки произвольной длины, сложные объекты без целочисленного ключа
• Когда важна сортировка «на месте» — Counting Sort требует O(n + k) дополнительной памяти

---

С объяснением логики работы

/**
 * Сортировка подсчётом (Counting Sort)
 * Принцип: считаем количество каждого значения, затем раскладываем элементы по местам.
 */
function countingSort(arr) {
    if (arr.length === 0) return arr;
 
    // 1. Находим диапазон значений
    const min = Math.min(...arr);
    const max = Math.max(...arr);
    const range = max - min + 1;
 
    // 2. Массив счётчиков: count[i] = сколько раз встречается значение (min + i)
    const count = new Array(range).fill(0);
    for (const num of arr) {
        count[num - min]++;
    }
 
    // 3. Префиксные суммы: count[i] = позиция, куда встанет следующий элемент значения i
    // Это делает сортировку СТАБИЛЬНОЙ
    for (let i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
 
    // 4. Строим результат, проходя исходный массив С КОНЦА (для стабильности)
    const result = new Array(arr.length);
    for (let i = arr.length - 1; i >= 0; i--) {
        const value = arr[i];
        count[value - min]--;
        result[count[value - min]] = value;
    }
 
    return result;
}
 
// Пример использования
console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]

---

С анализом сложностей

/**
 * Counting Sort с анализом сложности
 *
 * ВРЕМЕННАЯ СЛОЖНОСТЬ: O(n + k)
 * - n — количество элементов, k — размер диапазона (max - min + 1)
 * - Подсчёт: O(n), префиксные суммы: O(k), раскладка: O(n)
 * - Итого O(n + k). При k ≈ n это линейная O(n) — быстрее любой сортировки сравнением O(n log n)
 *
 * ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ: O(n + k)
 * - O(k) на массив счётчиков + O(n) на результат
 *
 * ОСОБЕННОСТИ:
 * - Стабильная (при проходе с конца с префиксными суммами)
 * - НЕ in-place
 * - Не сравнивает элементы между собой — обходит нижнюю границу O(n log n) для сравнений
 */
function countingSort(arr) {
    if (arr.length === 0) return arr;
 
    const min = Math.min(...arr);           // O(n)
    const max = Math.max(...arr);           // O(n)
    const range = max - min + 1;            // O(1)
 
    const count = new Array(range).fill(0); // O(k) память
    for (const num of arr) count[num - min]++; // O(n)
 
    for (let i = 1; i < range; i++)         // O(k)
        count[i] += count[i - 1];
 
    const result = new Array(arr.length);   // O(n) память
    for (let i = arr.length - 1; i >= 0; i--) { // O(n)
        const value = arr[i];
        count[value - min]--;
        result[count[value - min]] = value;
    }
 
    return result;
}

См. также

• radix-sort — использует counting sort по разрядам
• bucket-sort — тоже распределяющая сортировка
• O(n) — линейная сложность