Гоша: Если возможно сортировать данные за линейное время, почему в стандартных библиотеках применяют алгоритмы, которые работают за
O(nlogn)?
Тимофей: Сортировка подсчетом (англ. counting) работает за линейное время. Но дело в том, что у этого алгоритма есть ограничения, из-за которых его использование не всегда возможно.
Рассмотрим, как работаем алгоритм сортировки подсчётом.
Дан массив чисел:
Скопировать кодPYTHON
nums = [5, 7, 1, 0, 1, 5, 11, 1]
Вы хотите отсортировать его по неубыванию.
Вы знаете, что числа в нём обозначают номера месяцев.
То есть значения в массиве находятся в диапазоне от 0 до 11.
Заведём массив из 12 элементов, заполненный нулями.
Скопировать кодPYTHON
months = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Теперь пройдём по массиву nums и посчитаем сколько раз нам встретился каждый элемент. Добавим единицу в массив months по индексу, соответствующему каждому элементу
Первым мы встретили число 5. Добавим 1 в элемент массива months с индексом 5.
Скопировать кодPYTHON
months = [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
Далее идёт число 7. Увеличим на 1 число в ячейке с индексом 7.
Скопировать кодPYTHON
months = [0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
Повторим эти операции со всеми элементами, пока не закончится массив nums.
В результате получим такой массив months:
Скопировать кодPYTHON
months = [1, 3, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1]
Теперь, используя этот массив months, получим nums в отсортированном виде.
Для этого возьмём пустой массив sorted_nums. Затем пройдём по элементам массива months и добавим их в массив sorted_nums с учётом их количества.
Скопировать кодPYTHON
sorted_nums = [0, 1, 1, 1, 5, 5, 7, 11]
Так работает алгоритм сортировки подсчётом.