Сортировка подсчетом на Python

Программа будет сортировать список методом подсчета (Counting sort).

Алгоритм

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

Сложность сортировки по времени

1. Худшая O(n + k)
2. Средняя O(n + k)
3. Лучшая O(n)

Шаги к правильному решению

1. Создадим функцию counting_sort, которая принимает на вход список и переменную largest.
2. Внутри функции создадим список c нулями и длиной largest+1.
3. Для каждого элемента входного списка увеличиваем значение элемента таким образом c[alist[i]] = c[alist[i]] + 1.
4. Теперь список с содержит частоту каждого элемента входного списка.
5. Каждому элементу от 1 до length(c) -1 добавляем к значению текущего элемента значение предыдущего c[i] = c[i] + c[i - 1].
6. Создадим result список с таким же размером, как и входной список.
7. Создадим цикл, который итерируется по списку в обратном порядке.
8. В каждой итерации цикла установим result[c[x]] = x, а затем уменьшим c[x] на 1.

def counting_sort(alist, largest):
    c = [0]*(largest + 1)
    for i in range(len(alist)):
        c[alist[i]] = c[alist[i]] + 1
 
    # Find the last index for each element
    c[0] = c[0] - 1 # to decrement each element for zero-based indexing
    for i in range(1, largest + 1):
        c[i] = c[i] + c[i - 1]
 
    result = [None]*len(alist)
 
    # Though it is not required here,
    # it becomes necessary to reverse the list
    # when this function needs to be a stable sort
    for x in reversed(alist):
        result[c[x]] = x
        c[x] = c[x] - 1
 
    return result
 
 
alist = input('Enter the list of (nonnegative) numbers: ').split()
alist = [int(x) for x in alist]
k = max(alist)
sorted_list = counting_sort(alist, k)
print('Sorted list: ', end='')
print(sorted_list)