Учебник по информатике и математике
Темы
C++
Основы языка
Сортировка подсчетом
Оглавление:
Учительница проверила контрольную и хочет выписать оценки класса по возрастанию. Сравнивать тетради попарно ей незачем: оценок всего четыре вида. Она считает, сколько получилось двоек, троек, четверок и пятерок, а потом выписывает подряд все двойки, затем все тройки и так далее.
Это сортировка подсчетом. Она не сравнивает элементы между собой и поэтому бывает быстрее любой сортировки сравнениями. Но работает она только там, где значения — небольшие целые числа.
Идея алгоритма
Пусть все значения — целые числа от lo до hi. Заведем массив счетчиков cnt длины $k = hi - lo + 1$, по ячейке на каждое возможное значение. Значение x будем считать в ячейке cnt[x - lo]: наименьшее значение попадает в ячейку 0, следующее — в ячейку 1 и так далее.
- Проходим по массиву и для каждого
xувеличиваемcnt[x - lo]на 1. - Проходим по счетчикам по порядку и выписываем каждое значение столько раз, сколько оно встретилось.
Ключевая идея: Значение само указывает, в какую ячейку его положить. Поэтому сортировка подсчетом обходит предел сортировок сравнениями: им в худшем случае нужно порядка $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, когда в данных есть отрицательные числа. В Pythoncnt[-1]не вызывает ошибку: это последняя ячейка списка, и программа молча выдаст неверный ответ. В C++ отрицательный индекс — выход за границы массива и непредсказуемое поведение программы.
Проверь себя
Для каких данных сортировка подсчетом подходит лучше всего?
Массив [3, 0, 2, 3, 3, 1] сортируют подсчетом. Здесь lo = 0, поэтому число x считается в ячейке cnt[x]. Чему равно cnt[3] после подсчета?
Соедини обозначение и его смысл.
$n$
Время работы sorted() и std::sort
$k$
Количество возможных значений: hi - lo + 1
$O(n + k)$
Время работы сортировки подсчетом
$O(n \log n)$
Количество элементов массива