Программа будет сортировать список методом подсчета (Counting sort).
Подсчитываем, сколько раз в массиве встречается каждое значение, и заполняем массив подсчитанными элементами в соответствующих количествах. Счётчики для всего диапазона чисел создаются заранее (изначально равны нулю).
counting_sort
, которая принимает на вход список и переменную largest
.largest+1
.c[alist[i]] = c[alist[i]] + 1
.length(c) -1
добавляем к значению текущего элемента значение предыдущего c[i] = c[i] + c[i - 1]
.result
список с таким же размером, как и входной список.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)
Python предлагает набор библиотек, удовлетворяющих различные потребности в визуализации, будь то академические исследования, бизнес-аналитика или…
В Python для представления данных в двоичной форме можно использовать байты. Из этой статьи вы…
В этой статье рассказывается о том, что такое Werkzeug и как Flask использует его для…
При работе с датами часто возникает необходимость прибавлять к дате или вычитать из нее различные…
В этом руководстве мы рассмотрим, как добавить социальную аутентификацию с помощью GitHub и Google в…
В этой статье мы рассмотрим, что такое подсказки типов и чем они могут быть полезны.…