Интересная задача для улучшения навыков работы со списками. К тому же она может встретиться на экзаменах или олимпиадах по программированию.
Отсортируйте список, состоящий из целых чисел от 0 до 100 включительно, по неубыванию. Сделать это нужно за один проход по списку, так как список может быть внушительным.
Вы скажите: "Элементарно! Функция sorted все сделает сама". И будете правы, но наша задача не просто отсортировать список, но и научиться лучше понимать как можно пользоваться списками. Тем более, что функция sorted решит эту задачу не за один проход по списку.
Решение может выглядеть так:
def CountSort(ls):
....qls = [0] * 101
....ans = []
....for i in range(len(ls)):
........qls[ls[i]] += 1
....for i in range(101):
........for j in range(qls[i]):
............ans.append(i)
return ans
ls = list(map(int, input().split()))
print(*CountSort(ls))
Итак, нам нужно за один проход по списку, создать какую-то структуру, которую потом можно конвертировать в отсортированный список. Роль этой структуры возьмет на себя (это гениально!) другой список.
Ключ решения этой задачи в том, что мы знаем все возможные числа, которые могут встретиться в исходном списке - числа от 0 до 100. Это дает нам возможность создать другой список, в котором будет 100 элементов, где значение каждого элемента равно нулю. qls = [0] * 101
"И что с того?" - спросите вы.
А теперь, перебирая в цикле все элементы исходного списка, для каждого элемента со значением i находим в новом списке элемент с индексом i и прибавляем к нему 1: qls[ls[i]] += 1. У нас получается список, в котором номер индекса - это возможные числа из заданного списка, а значение элемента списка с этим индексом - это сколько раз встретилось это число в заданном списке.
После завершения большого цикла по заданному списку мы берем пустой список ans = [], который и будет нашим искомым отсортированным списком. Делаем цикл по списку, состоящему из 100 элементов и для каждого элемента, не равного нулю, добавляем к концу с нового финального списка элемент со значением индекса. Делаем это в цикле, число повторений равно значению элемента:
for j in range(qls[i]):
....ans.append(i)
В результате получаем список, состоящий из тех же чисел что и заданный список, и повторяющихся столько же раз, сколько они встречаются в начальном списке.
А если в списке есть отрицательные числа? Как быть?
Таким способом можно сортировать и списки с отрицательными числами, например от -100 до 100. Решение будет таким:
ls = input().split()
qls = [0] * 201
for i in ls:
....qls[int(i)] += 1
ans = []
for i in range(-100, 101):
....for j in range(qls[i]):
........ans.append(i)
print(*ans)
В цикле for i in range(-100, 101): сначала беруться числа с индексами от 101 до 200, так как например индекс -100 это значит взять сотый элемент справа (что то же самое, что сто первый элемент слева). Затем перебираются элементы с индексами от 0 до 100 слева, то есть положительные числа. Таким образом в список ans.append(i) добавляются сначала отрицательные числа (qls[-100]....qls[-1]), а затем положительные (qls[0]....qls[100]).
Если язык программирования не поддерживает отрицательные индексы, то можно просто при заполнении списка qls[] прибавлять 100:
qls[int(i + 100)] += 1, а при заполнении списка ans[] вычитать 100:
ans.append(i - 100)
А если массив не 100, а 100 миллионов?
Рассмотренный алгоритм это частным случай поразрядной сортировки. Если требуется отсортировать массив с числами от 0 до 100000000, то в этом случае можно сначала отсортировать, рассмотренным выше алгоритмом, числа по последним двум разрядам, потом по двум предпоследним разрядам и т.д.
Так же есть схожий алгоритм суффиксного массива. Но это уже не тема данной статьи.
Заключение.
Поначалу функция sorted конечно будет работать быстрее нашей програмки, но при увеличении входных данных наступит момент, с которого наш алгоритм будет выигрывать по времени.
