counting.md

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

| Главная | Сортировки |

Сортировка подсчётом (англ. counting sort) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

Реализация

• Устойчивый вариант

Лучшее время	Среднее время	Худшее время	Память	Устойчивая	Обмены в среднем
O(n)	O(n + k)	O(k)	O(k)	+	O(n + k)

def counting_sort(nums):
    min_num = min(nums) # O(n)
    max_num = max(nums) # O(n)
    
    counter = dict()
    for num in nums:
        if num not in counter:
            counter[num] = 0
        counter[num] += 1
        
    sorted_nums = []
    for key in range(min_num, max_num + 1):
        if key not in counter:
            continue
        for _ in range(counter[key]):
            sorted_nums.append(key)
    
    return sorted_nums
    
    
print(counting_sort([2, 2, 3, 4, 5, 6, 1, 2, 3, 4, 4, 5, 2, 2, 2, 1]))