Предыдущая часть
Ранее рассмотренные методы давали нам оценку сложности не лучше чем O(N²), так что, конечно, возникает вопрос – а можно ли её вообще улучшить? Да, но только это всегда будет приводить к некоторым ограничениям.
Сортировка подсчётом
Весьма оригинальный и супер-простой метод сортировки. Если на входе нам дан массив целых чисел, где каждое число находится в диапазоне от 0 до R, то после сортировки мы должны получить ряд возрастающих чисел:
0, 1, 2, 3, 4, 5, 6, ... R
Но не все числа могут в нём присутствовать, а некоторые числа могут повторяться несколько раз. То есть реально это может выглядеть примерно так:
2, 3, 3, 3, 10, 187, 220, 500, 500, ...
Идея состоит в том, чтобы просто посчитать, сколько раз каждое число из диапазона 0..R встречается в массиве, и вставить его сразу в нужное место ряда. Оно может не встречаться вообще, встречаться 1 раз, или встречаться несколько раз. Для каждого уникального числа заводится счётчик. Итого нужно R+1 счётчиков, или массив из R+1 элементов:
[0, 0, 0, 0, 0, ...] ← R+1 элементов
Позиция каждого счётчика в массиве соответствует самому числу, которое он считает. Счётчик для числа 0 находится в позиции 0, счётчик для числа 1 в позиции 1, и т.д.
Это значит, что массив счётчиков уже отсортирован!
Чтобы его заполнить, нужно пройти по массиву чисел всего один раз. Мы берём первое число. Допустим, оно равно 5. Тогда мы в массиве счётчиков увеличиваем счётчик в позиции 5. Мы посчитали это число. Берём следующее. Допустим, оно равно 3. Тогда массиве счётчиков мы увеличиваем счётчик в позиции 3. И его посчитали. Массив счётчиков пока будет выглядеть так:
[0, 0, 0, 1, 0, 1, 0, 0, ...]
Единицы стоят в 3-й и в 5-й позиции. То есть числа 3 и 5 уже отмечены на своих местах, они уже отсортированы.
Так мы доходим до конца массива с числами и заполняем все счётчики.
Чтобы получить окончательный отсортированный массив, нужно теперь пройти по массиву счётчиков и последовательно, друг за другом переписать все числа в нужных количествах в сортируемый массив.
Таким образом, каждый непустой счётчик просто дописывает в массив свою позицию столько раз, сколько он насчитал.
Пишем на Python (если не помещается, см. ссылку):
И всё, мы получаем отсортированный массив. Для этого потребовалось всего лишь:
- 1 раз пройти по сортируемому массиву (N повторений)
- 1 раз пройти по массиву счётчиков (R повторений)
Следовательно, сложность данного алгоритма мы оценим как O(N + R).
Можно ли сказать, что асимптотическая сложность будет O(N), ведь R мало влияет при N→∞? Нет, R это не множитель и не константа, это отдельный, независимый параметр алгоритма. Если N задаёт количество элементов массива, то R задаёт максимальное значение элемента. А это, в свою очередь, определяет размер массива счётчиков.
Например, если элементов всего 5, но каждый элемент имеет значение 0..999, то для сортировки массива из 5 элементов потребуется массив из 1000 счётчиков.
В этом и заключается недостаток данного алгоритма. Кроме собственно количества операций, для выполнения ему также нужна оперативная память, и вполне возможно, что ОЧЕНЬ много.
Если мы сортируем массив 8-битных чисел, то для хранения счётчиков понадобится всего 256 позиций. Для сортировки 16-битных чисел понадобится 65536 позиций. Ну а если числа будут 32-битные, то понадобятся 4 миллиарда счётчиков. Причём они понадобятся в любом случае, даже если надо отсортировать всего лишь 10 чисел.
Частично обойти эту проблему можно, если заранее найти самое большое число в массиве.
Кроме того, этот алгоритм нельзя применять на всех типах данных. Например, как отсортировать вещественные числа? Мы не можем обратиться в массиве к позиции, которая не является целым числом.
Но для сортировки большого массива из 8- или 16-битных целых чисел вы вряд ли найдёте что-то лучше.
Следующая часть: алгоритм quicksort