Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

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

    Оглавление:

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

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

    Идея алгоритма

    Пусть все значения — целые числа от lo до hi. Заведем массив счетчиков cnt длины $k = hi - lo + 1$, по ячейке на каждое возможное значение. Значение x будем считать в ячейке cnt[x - lo]: наименьшее значение попадает в ячейку 0, следующее — в ячейку 1 и так далее.

    1. Проходим по массиву и для каждого x увеличиваем cnt[x - lo] на 1.
    2. Проходим по счетчикам по порядку и выписываем каждое значение столько раз, сколько оно встретилось.

    Ключевая идея: Значение само указывает, в какую ячейку его положить. Поэтому сортировка подсчетом обходит предел сортировок сравнениями: им в худшем случае нужно порядка $n \log n$ сравнений, и это доказано.

    Разбор на примере

    Оценки: [5, 3, 4, 5, 2, 4, 5, 3]. Здесь lo = 2, hi = 5, значит, счетчиков четыре.

    Оценка x Ячейка x - 2 Сколько раз встретилась
    2 0 1
    3 1 2
    4 2 2
    5 3 3

    После первого прохода cnt = [1, 2, 2, 3]. Выписываем одну двойку, две тройки, две четверки и три пятерки: [2, 3, 3, 4, 4, 5, 5, 5]. Мы ни разу не сравнили две оценки, чтобы решить, какая должна стоять раньше.

    Реализация

    Код сам находит lo и hi, поэтому справляется и с отрицательными числами. Если диапазон известен заранее (оценки всегда от 2 до 5), искать их не нужно.

    def counting_sort(a):
        if not a:
            return []
        lo, hi = min(a), max(a)
        cnt = [0] * (hi - lo + 1)        # счетчик для каждого значения от lo до hi
        for x in a:
            cnt[x - lo] += 1
        result = []
        for i in range(len(cnt)):
            result += [i + lo] * cnt[i]  # значение i + lo повторяем cnt[i] раз
        return result
    
    
    marks = [5, 3, 4, 5, 2, 4, 5, 3]
    print(counting_sort(marks))              # [2, 3, 3, 4, 4, 5, 5, 5]
    print(counting_sort([3, -1, 0, -1, 2]))  # [-1, -1, 0, 2, 3]
    

    На C++ результат записываем прямо в исходный массив, позиция для записи — pos:

    #include <algorithm>
    #include <iostream>
    #include <vector>
    using namespace std;
    
    void countingSort(vector<int>& a) {
        if (a.empty()) return;
        int lo = *min_element(a.begin(), a.end());
        int hi = *max_element(a.begin(), a.end());
        vector<int> cnt(hi - lo + 1, 0);
        for (int x : a) cnt[x - lo]++;
        int pos = 0;
        for (int v = lo; v <= hi; v++)
            for (int c = 0; c < cnt[v - lo]; c++)
                a[pos++] = v;
    }
    
    int main() {
        vector<int> marks = {5, 3, 4, 5, 2, 4, 5, 3};
        countingSort(marks);
        for (int x : marks) cout << x << " ";  // 2 3 3 4 4 5 5 5
        cout << "\n";
    }
    

    Сложность

    Поиск lo и hi и подсчет — это проходы по массиву, по $n$ шагов каждый. Выписывание проходит по $k$ счетчикам и записывает $n$ элементов. Итого время $O(n + k)$, а память под счетчики — $O(k)$.

    Когда $k$ маленькое, это очень быстро. Миллион оценок сортируется примерно за несколько миллионов простых шагов, а встроенной сортировке понадобится порядка $n \log_2 n \approx 20$ миллионов сравнений. Но если числа большие, $k$ становится огромным: чтобы отсортировать всего два числа, 1 и 1 000 000 000, понадобится миллиард счетчиков — несколько гигабайт памяти.

    Данные Подходит?
    Оценки от 2 до 5, возраст, баллы ЕГЭ от 0 до 100 да: значений мало
    Числа до $10^9$, номера телефонов нет: слишком много возможных значений
    Дробные числа, строки нет: значение нельзя сделать номером ячейки

    Если сортировать не сами числа, а записи — например, учеников по оценке, — используют вариант с накопленными суммами счетчиков. По ним вычисляют, с какой позиции в ответе начинается каждая оценка, и раскладывают учеников по местам. Такой вариант сохраняет порядок учеников с одинаковой оценкой, и на нем построена поразрядная сортировка.

    Частая ошибка: Массив счетчиков без сдвига x - lo, когда в данных есть отрицательные числа. В Python cnt[-1] не вызывает ошибку: это последняя ячейка списка, и программа молча выдаст неверный ответ. В C++ отрицательный индекс — выход за границы массива и непредсказуемое поведение программы.

    Проверь себя

    1.

    Для каких данных сортировка подсчетом подходит лучше всего?

    2.

    Массив [3, 0, 2, 3, 3, 1] сортируют подсчетом. Здесь lo = 0, поэтому число x считается в ячейке cnt[x]. Чему равно cnt[3] после подсчета?

    3.

    Соедини обозначение и его смысл.

    $n$

    Время работы sorted() и std::sort

    $k$

    Количество возможных значений: hi - lo + 1

    $O(n + k)$

    Время работы сортировки подсчетом

    $O(n \log n)$

    Количество элементов массива

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами