Сортировка подсчетом: интерактивная анимация (Counting Sort)

Сложность алгоритма

Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Ресурса у алгоритма два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.

По времени

Показывает, как растет число операций (здесь это чтения и записи, сравнений нет вовсе) при росте n. Лейбл "Сложность" под визуализацией - время, которое получилось фактически на ваших данных.

По памяти

Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него.

Устойчивость алгоритма

Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов. Пример: сортируем учеников по оценке, а внутри одной оценки они уже стояли по алфавиту. Устойчивая сортировка сохранит алфавитный порядок внутри каждой оценки, неустойчивая - может перемешать.

Примеры реализации сортировки подсчетом (Counting Sort)

Код на C

void countingSort(int arr[], int n, int max_val) {
    // 1. Создаем массив счетчиков (k = max_val + 1)
    int k = max_val + 1;
    int* counts = (int*)calloc(k, sizeof(int));
    
    // 2. Фаза подсчета
    for (int i = 0; i < n; i++) {
        counts[arr[i]]++;
    }
    
    // 3. Фаза сборки результата
    int index = 0;
    for (int i = 0; i < k; i++) {
        while (counts[i] > 0) {
            arr[index] = i;
            index++;
            counts[i]--;
        }
    }
    
    free(counts);
}

Код на Python

def counting_sort(arr, max_val):
    # 1. Создаем массив счетчиков
    counts = [0] * (max_val + 1)
    
    # 2. Фаза подсчета
    for num in arr:
        counts[num] += 1
        
    # 3. Фаза сборки результата
    index = 0
    for i in range(len(counts)):
        while counts[i] > 0:
            arr[index] = i
            index += 1
            counts[i] -= 1

Код на JavaScript

function countingSort(arr, maxVal) {
    // 1. Создаем массив счетчиков
    const counts = new Array(maxVal + 1).fill(0);
    
    // 2. Фаза подсчета
    for (let i = 0; i < arr.length; i++) {
        counts[arr[i]]++;
    }
    
    // 3. Фаза сборки результата
    let index = 0;
    for (let i = 0; i < counts.length; i++) {
        while (counts[i] > 0) {
            arr[index] = i;
            index++;
            counts[i]--;
        }
    }
    return arr;
}

Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про сортировку подсчетом - с подробной теорией, задачами и проверочными вопросами.