Counting и Radix Sort

Нижняя граница сортировок сравнением

Любая сортировка, основанная на сравнениях, не может быть быстрее O(n log n). Это доказано через дерево решений.

Но если мы знаем что-то о данных (например, это целые числа в ограниченном диапазоне), можно обойти это ограничение.

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

Идея: подсчитать количество каждого элемента, затем восстановить массив.

Ограничение: работает только для целых неотрицательных чисел в известном диапазоне.

<?php
declare(strict_types=1);

/** @return list<int> */
function countingSort(array $arr): array
{
    if ($arr === []) {
        return [];
    }

    $maxVal = max($arr);
    $count = array_fill(0, $maxVal + 1, 0);

    // Count occurrences
    foreach ($arr as $num) {
        $count[$num]++;
    }

    // Reconstruct
    $result = [];
    for ($num = 0; $num <= $maxVal; $num++) {
        for ($i = 0; $i < $count[$num]; $i++) {
            $result[] = $num;
        }
    }

    return $result;
}

// [4, 2, 2, 8, 3, 3, 1]
// count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
//          0  1  2  3  4  5  6  7  8
// result = [1, 2, 2, 3, 3, 4, 8]

import "slices"

func countingSort(arr []int) []int {
    if len(arr) == 0 {
        return nil
    }

    maxVal := slices.Max(arr)
    count := make([]int, maxVal+1)

    // Count occurrences
    for _, num := range arr {
        count[num]++
    }

    // Reconstruct
    result := make([]int, 0, len(arr))
    for num := 0; num <= maxVal; num++ {
        for i := 0; i < count[num]; i++ {
            result = append(result, num)
        }
    }

    return result
}

// [4, 2, 2, 8, 3, 3, 1]
// count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
//          0  1  2  3  4  5  6  7  8
// result = [1, 2, 2, 3, 3, 4, 8]

static List<int> CountingSort(List<int> arr)
{
    if (arr.Count == 0)
    {
        return [];
    }

    int maxVal = arr.Max();
    int[] count = new int[maxVal + 1];

    // Count occurrences
    foreach (int num in arr)
    {
        count[num]++;
    }

    // Reconstruct
    List<int> result = new(arr.Count);
    for (int num = 0; num <= maxVal; num++)
    {
        for (int i = 0; i < count[num]; i++)
        {
            result.Add(num);
        }
    }

    return result;
}

// [4, 2, 2, 8, 3, 3, 1]
// count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
//          0  1  2  3  4  5  6  7  8
// result = [1, 2, 2, 3, 3, 4, 8]

def counting_sort(arr: list[int]) -> list[int]:
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    # Count occurrences
    for num in arr:
        count[num] += 1

    # Reconstruct
    result: list[int] = []
    for num, freq in enumerate(count):
        result.extend([num] * freq)

    return result

# [4, 2, 2, 8, 3, 3, 1]
# count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
#          0  1  2  3  4  5  6  7  8
# result = [1, 2, 2, 3, 3, 4, 8]

### Стабильная версия Counting Sort

<?php
declare(strict_types=1);

/** @return list<int> */
function countingSortStable(array $arr): array
{
    if ($arr === []) {
        return [];
    }

    $maxVal = max($arr);
    $count = array_fill(0, $maxVal + 1, 0);

    foreach ($arr as $num) {
        $count[$num]++;
    }

    // Prefix sum for positions
    for ($i = 1; $i <= $maxVal; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // Fill result in reverse order (for stability)
    $n = count($arr);
    $result = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $num = $arr[$i];
        $count[$num]--;
        $result[$count[$num]] = $num;
    }

    return $result;
}

func countingSortStable(arr []int) []int {
    if len(arr) == 0 {
        return nil
    }

    maxVal := slices.Max(arr)
    count := make([]int, maxVal+1)

    for _, num := range arr {
        count[num]++
    }

    // Prefix sum for positions
    for i := 1; i <= maxVal; i++ {
        count[i] += count[i-1]
    }

    // Fill result in reverse order (for stability)
    n := len(arr)
    result := make([]int, n)

    for i := n - 1; i >= 0; i-- {
        num := arr[i]
        count[num]--
        result[count[num]] = num
    }

    return result
}

static int[] CountingSortStable(int[] arr)
{
    if (arr.Length == 0)
    {
        return [];
    }

    int maxVal = arr.Max();
    int[] count = new int[maxVal + 1];

    foreach (int num in arr)
    {
        count[num]++;
    }

    // Prefix sum for positions
    for (int i = 1; i <= maxVal; i++)
    {
        count[i] += count[i - 1];
    }

    // Fill result in reverse order (for stability)
    int n = arr.Length;
    int[] result = new int[n];

    for (int i = n - 1; i >= 0; i--)
    {
        int num = arr[i];
        count[num]--;
        result[count[num]] = num;
    }

    return result;
}

def counting_sort_stable(arr: list[int]) -> list[int]:
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    # Prefix sum for positions
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]

    # Fill result in reverse order (for stability)
    n = len(arr)
    result = [0] * n

    for i in range(n - 1, -1, -1):
        num = arr[i]
        count[num] -= 1
        result[count[num]] = num

    return result

**Сложность:** O(n + k), где k — диапазон значений. Память: O(k).

Radix Sort (поразрядная сортировка)

Идея: сортировать числа поразрядно, начиная с младшего разряда, используя стабильную сортировку (Counting Sort) для каждого разряда.

Массив: [170, 45, 75, 90, 802, 24, 2, 66]

По единицам (1-й разряд):
170, 90, 802, 2, 24, 45, 75, 66

По десяткам (2-й разряд):
802, 2, 24, 45, 66, 170, 75, 90

По сотням (3-й разряд):
2, 24, 45, 66, 75, 90, 170, 802  <- отсортировано!

<?php
declare(strict_types=1);

/** @param list<int> $arr */
function radixSort(array &$arr): void
{
    if ($arr === []) {
        return;
    }

    $maxVal = max($arr);
    $exp = 1; // Current digit place (1, 10, 100, ...)

    while (intdiv($maxVal, $exp) > 0) {
        countingSortByDigit($arr, $exp);
        $exp *= 10;
    }
}

function countingSortByDigit(array &$arr, int $exp): void
{
    $n = count($arr);
    $output = array_fill(0, $n, 0);
    $count = array_fill(0, 10, 0); // Digits 0-9

    // Count by current digit
    foreach ($arr as $num) {
        $digit = intdiv($num, $exp) % 10;
        $count[$digit]++;
    }

    // Prefix sum
    for ($i = 1; $i < 10; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // Fill output (in reverse order for stability)
    for ($i = $n - 1; $i >= 0; $i--) {
        $digit = intdiv($arr[$i], $exp) % 10;
        $count[$digit]--;
        $output[$count[$digit]] = $arr[$i];
    }

    // Copy back
    $arr = $output;
}

func radixSort(arr []int) {
    if len(arr) == 0 {
        return
    }

    maxVal := slices.Max(arr)
    exp := 1 // Current digit place (1, 10, 100, ...)

    for maxVal/exp > 0 {
        countingSortByDigit(arr, exp)
        exp *= 10
    }
}

func countingSortByDigit(arr []int, exp int) {
    n := len(arr)
    output := make([]int, n)
    count := make([]int, 10) // Digits 0-9

    // Count by current digit
    for _, num := range arr {
        digit := (num / exp) % 10
        count[digit]++
    }

    // Prefix sum
    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    // Fill output (in reverse order for stability)
    for i := n - 1; i >= 0; i-- {
        digit := (arr[i] / exp) % 10
        count[digit]--
        output[count[digit]] = arr[i]
    }

    // Copy back
    copy(arr, output)
}

static void RadixSort(int[] arr)
{
    if (arr.Length == 0)
    {
        return;
    }

    int maxVal = arr.Max();

    // exp is the current digit place (1, 10, 100, ...)
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
    {
        CountingSortByDigit(arr, exp);
    }
}

static void CountingSortByDigit(int[] arr, int exp)
{
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10]; // Digits 0-9

    // Count by current digit
    foreach (int num in arr)
    {
        count[num / exp % 10]++;
    }

    // Prefix sum
    for (int i = 1; i < 10; i++)
    {
        count[i] += count[i - 1];
    }

    // Fill output (in reverse order for stability)
    for (int i = n - 1; i >= 0; i--)
    {
        int digit = arr[i] / exp % 10;
        count[digit]--;
        output[count[digit]] = arr[i];
    }

    // Copy back
    output.CopyTo(arr, 0);
}

def radix_sort(arr: list[int]) -> None:
    if not arr:
        return

    max_val = max(arr)
    exp = 1  # Current digit place (1, 10, 100, ...)

    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10

def counting_sort_by_digit(arr: list[int], exp: int) -> None:
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # Digits 0-9

    # Count by current digit
    for num in arr:
        count[num // exp % 10] += 1

    # Prefix sum
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Fill output (in reverse order for stability)
    for i in range(n - 1, -1, -1):
        digit = arr[i] // exp % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]

    # Copy back: slice assignment mutates the caller's list in place
    arr[:] = output

**Сложность:** O(d * (n + k)), где d — количество разрядов, k = 10 для десятичных. Для n чисел в диапазоне [0, n^c]: O(c * n) = **O(n)**.

Визуализация Radix Sort

Исходный: [329, 457, 657, 839, 436, 720, 355]

Разряд единиц (exp=1):
Bucket 0: [720]
Bucket 5: [355]
Bucket 6: [436]
Bucket 7: [457, 657]
Bucket 9: [329, 839]
-> [720, 355, 436, 457, 657, 329, 839]

Разряд десятков (exp=10):
Bucket 2: [720, 329]
Bucket 3: [436, 839]
Bucket 5: [355, 457, 657]
-> [720, 329, 436, 839, 355, 457, 657]

Разряд сотен (exp=100):
Bucket 3: [329, 355]
Bucket 4: [436, 457]
Bucket 6: [657]
Bucket 7: [720]
Bucket 8: [839]
-> [329, 355, 436, 457, 657, 720, 839]

Bucket Sort (для полноты)

Распределяем элементы по «корзинам», сортируем каждую, объединяем.

<?php
declare(strict_types=1);

/** @return list<float> */
function bucketSort(array $arr): array
{
    if ($arr === []) {
        return [];
    }

    $n = count($arr);
    $minVal = min($arr);
    $maxVal = max($arr);

    if ($minVal === $maxVal) {
        return $arr;
    }

    // Create buckets
    $bucketCount = $n;
    $bucketRange = ($maxVal - $minVal) / $bucketCount;
    $buckets = array_fill(0, $bucketCount + 1, []);

    foreach ($arr as $num) {
        $idx = (int) (($num - $minVal) / $bucketRange);
        $buckets[$idx][] = $num;
    }

    // Sort each bucket and merge
    $result = [];
    foreach ($buckets as &$bucket) {
        sort($bucket); // Insertion sort for small buckets
        foreach ($bucket as $val) {
            $result[] = $val;
        }
    }

    return $result;
}

import "sort"

func bucketSort(arr []float64) []float64 {
    if len(arr) == 0 {
        return nil
    }

    n := len(arr)
    minVal, maxVal := arr[0], arr[0]
    for _, v := range arr {
        if v < minVal {
            minVal = v
        }
        if v > maxVal {
            maxVal = v
        }
    }

    if minVal == maxVal {
        result := make([]float64, n)
        copy(result, arr)
        return result
    }

    // Create buckets
    bucketCount := n
    bucketRange := (maxVal - minVal) / float64(bucketCount)
    buckets := make([][]float64, bucketCount+1)

    for _, num := range arr {
        idx := int((num - minVal) / bucketRange)
        buckets[idx] = append(buckets[idx], num)
    }

    // Sort each bucket and merge
    result := make([]float64, 0, n)
    for _, bucket := range buckets {
        sort.Float64s(bucket) // Sort small buckets
        result = append(result, bucket...)
    }

    return result
}

static List<double> BucketSort(List<double> arr)
{
    if (arr.Count == 0)
    {
        return [];
    }

    int n = arr.Count;
    double minVal = arr.Min();
    double maxVal = arr.Max();

    if (minVal == maxVal)
    {
        return [.. arr];
    }

    // Create buckets
    int bucketCount = n;
    double bucketRange = (maxVal - minVal) / bucketCount;
    List<double>[] buckets = new List<double>[bucketCount + 1];
    for (int i = 0; i < buckets.Length; i++)
    {
        buckets[i] = [];
    }

    foreach (double num in arr)
    {
        int idx = (int)((num - minVal) / bucketRange);
        buckets[idx].Add(num);
    }

    // Sort each bucket and merge
    List<double> result = new(n);
    foreach (List<double> bucket in buckets)
    {
        bucket.Sort(); // Sort small buckets
        result.AddRange(bucket);
    }

    return result;
}

def bucket_sort(arr: list[float]) -> list[float]:
    if not arr:
        return []

    n = len(arr)
    min_val = min(arr)
    max_val = max(arr)

    if min_val == max_val:
        return list(arr)

    # Create buckets
    bucket_count = n
    bucket_range = (max_val - min_val) / bucket_count
    buckets: list[list[float]] = [[] for _ in range(bucket_count + 1)]

    for num in arr:
        idx = int((num - min_val) / bucket_range)
        buckets[idx].append(num)

    # Sort each bucket and merge
    result: list[float] = []
    for bucket in buckets:
        bucket.sort()  # Timsort handles small buckets efficiently
        result.extend(bucket)

    return result

**Сложность:** O(n) в среднем при равномерном распределении, O(n²) в худшем.

Сравнение не-сравнительных сортировок

Алгоритм	Время	Память	Стабильная	Ограничения
Counting Sort	O(n + k)	O(k)	Да	Целые числа, малый k
Radix Sort	O(d * (n + k))	O(n + k)	Да	Целые числа
Bucket Sort	O(n) средн.	O(n + k)	Да	Равномерное распределение

Общая таблица всех сортировок

Алгоритм	Лучший	Средний	Худший	Память	Стабильная
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Да
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Нет
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Да
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Да
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	Нет
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	Нет
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Да
Radix Sort	O(dn)	O(dn)	O(dn)	O(n+k)	Да

Запомни: Counting Sort = O(n+k), идеален когда k (диапазон) невелик. Radix Sort = O(dn), для чисел с фиксированным количеством разрядов. Оба обходят нижнюю границу O(n log n) потому что НЕ основаны на сравнениях. На интервью: если данные — целые числа в известном диапазоне, предложи Counting Sort.

Итоги

Counting Sort: O(n+k), для малых целых чисел
Radix Sort: O(d*n), сортирует поразрядно через Counting Sort
Обе обходят O(n log n) за счёт знаний о данных
Counting Sort — основа для Radix Sort (стабильная)
На практике: для строк, дат, IP-адресов — Radix Sort