Алгоритмы и структуры данных. Лекция 7. Сортировка подсчетом (Counting sort) на Python | MADTeacher | Дзен

• Временная сложность: O n + k, где k - количество уникальных значений.  

• Память: O k, что делает алгоритм неэффективным при большом разбросе значений и жестких требованиях по памяти.  

• Используется диапазон чисел сортируемого массива и подсчет количества вхождений каждого элемента.  

• Находим максимальный и минимальный элементы массива.  

• Строим новый массив длиной, равной разнице между максимальным и минимальным элементами.  

• Заносим частоту повторений и двигаемся слева направо, перенося элементы в результирующий массив.  

• Подходит для сортировки целочисленных значений.  

• Находим минимальное и максимальное значения.  

• Строим список для хранения частоты повторений.  

• Проходим по массиву, увеличивая частоту и перенося повторения в результирующий список.  

• В итоге получаем отсортированный список по возрастанию.  

• Для подсчета частоты вхождения используйте словарь.  

• Сформируйте список из ключей словаря и отсортируйте его по возрастанию или убыванию.  

• Заполните результирующий список, используя отсортированный список.