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

Определение

Главная идея алгоритма — посчитать, сколько раз встречается каждый элемент в массиве, а потом заполнить исходный массив результатами этого подсчёта. Для этого нам нужен вспомогательный массив, где мы будем хранить результаты подсчёта. Даже если нам надо отсортировать миллион чисел, мы всё равно знаем диапазон этих чисел заранее, например, от 1 до 100. Это значит, что во вспомогательном массиве будет не миллион элементов, а сто.

1. Создание счетного массива: Создаем счетный массив для хранения количества вхождений каждого элемента.
2. Подсчет элементов: Подсчитываем количество каждого элемента в исходном массиве.
3. Изменение счетного массива: Преобразуем счетный массив так, чтобы он показывал конечные позиции элементов.
4. Заполнение выходного массива: Проходим по исходному массиву в обратном порядке, чтобы элементы с одинаковым значением размещались в правильном порядке, сохраняя их первоначальный порядок появления.

def countingSort(arr):  
    if not arr:  
        return arr  
	  
    maxVal = max(arr)  
    minVal = min(arr)  
	  
    rangeOfElements = maxVal - minVal + 1  
    countArr = [0] * rangeOfElements  
	  
    for num in arr:  
        countArr[num - minVal] += 1  
	  
    for i in range(1, rangeOfElements):  
        countArr[i] += countArr[i - 1]  
	  
    outputArr = [0] * len(arr)  
	  
    for num in reversed(arr):  
        outputArr[countArr[num - minVal] - 1] = num  
        outputArr[num - minVal] -= 1  
	  
    return outputArr