Counting Sort
Алгоритмы, подобные Merge Sort, выполняют операций, чтобы отсортировать заданную последовательность элементов. Большинство встроенных функций
sort() в разных языках программирования также работают за . Возникает закономерный вопрос — можно ли отсортировать ещё быстрее?Один из базовых алгоритмов, который умеет сортировать последовательность элементов за линейное время (то есть выполняет операций), — это Counting Sort (сортировка подсчётом). Такой подход особенно эффективен, когда мы имеем дело с набором элементов, представляющих собой небольшие целые числа.
Основная идея Counting Sort заключается в том, чтобы с помощью структуры, напоминающей гистограмму, подсчитать, сколько раз встречается каждое возможное значение во входном массиве. После этого на основе полученных подсчётов элементы массива распределяются в итоговую последовательность в отсортированном порядке.
Например, чтобы отсортировать массив со значениями
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], мы строим гистограмму, которая показывает количество каждого числа, встречающегося в массиве, к примеру: [6, 2, 5, 4, 5, 1, 6, 1] (как показано на рисунке).
a = ...
bottom, top = min(a), max(a) + 1 # Determine the range
hist = [0] * (top - bottom) # Fill the range with 0s => no counts
for num in a: # Iterate through the array
hist[num - bottom] += 1 # Increase the histogram value
res = [] # Initialize the result array
for num in range(bottom, top): # Iterate over the range
res += [num] * hist[num - bottom] # Add as many nums to result as the value in the histogramВ результате получится массив
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].Обратите внимание: такой подход работает только с числами, причём желательно с небольшим диапазоном значений. В то же время, другие алгоритмы вроде Bubble sort или Merge sort могут обрабатывать любые элементы, которые можно сравнивать между собой.
Таким образом, алгоритм Counting Sort в сумме выполняет операций, где
n — это количество элементов в исходном массиве, а r — размер диапазона возможных значений. Когда диапазон сравнительно небольшой, это может работать значительно быстрее, чем, к примеру, Merge sort.🤔
Существуют ли другие алгоритмы, работающие за линейное время?
Да, можно обратить внимание на Radix-sort. Однако и он подходит только для чисел.
Если же мы рассматриваем только алгоритмы, основанные на сравнении (которые подходят для сортировки любых типов данных при условии, что элементы сравнимы), тогда лучшие из них работают за , и ускорить этот показатель уже не получится.
Входные данные
В первой строке входных данных содержится одно целое число
n (1 ≤ n ≤ ).Во второй строке указаны
n целых чисел (-100 ≤ ≤ 100).Выходные данные
Программа должна вывести
n чисел, расположенных по возрастанию, разделяя их одним пробелом.Примеры
Ввод | Вывод |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB