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

Ответ от Vasiliy Ganov[мастер]
У тебя есть массив A[10], состоящий из элементов 7, 3, 5, 5, 3, 7, 7, 3, 5, 5.
Создаем вспомогательный массив C[10], в котором все элементы нулевые.
I) Последовательно читаем элементы массива A. Для каждого A[ i ] увеличиваем на единицу С [A[ i ]] (т. е. элемент массива C, имеющий номер, равный значению элемента массива А) :
A 7 3 5 5 3 7 7 3 5 5
С 0 0 0 0 0 0 0 0 0 0
1) 0 0 0 0 0 0 0 1 0 0 - мы увеличили 7-ой элемент С, т. к. первый элемент А равен 7
2) 0 0 0 1 0 0 0 1 0 0 - мы увеличили 3-ой элемент С, т. к. второй элемент А равен 3
3) 0 0 0 1 0 1 0 1 0 0
4) 0 0 0 1 0 2 0 1 0 0
5) 0 0 0 2 0 2 0 1 0 0
6) 0 0 0 2 0 2 0 2 0 0
7) 0 0 0 2 0 2 0 3 0 0
8) 0 0 0 3 0 2 0 3 0 0
9) 0 0 0 3 0 3 0 3 0 0
10)0 0 0 3 0 4 0 3 0 0 - так выглядит после всех итераций массив С
Означает это, что у нас есть 3 тройки, 4 пятерки и 3 семерки.
II) Теперь нужно пройти по массиву С, записывая в массив A текущий номер i элемента массива С С [ i ] раз:
A 7 3 5 5 3 7 7 3 5 5
С 0 0 0 3 0 4 0 3 0 0
1) 7 3 5 5 3 7 7 3 5 5 - записываем в массив A текущий номер 0 элемента массива С 0 раз (т. е. не записываем)
2) 7 3 5 5 3 7 7 3 5 5 - записываем в массив A текущий номер 1 элемента массива С 0 раз
3) 7 3 5 5 3 7 7 3 5 5 - записываем в массив A текущий номер 2 элемента массива С 0 раз
4) 3 3 3 5 3 7 7 3 5 5 - записываем в массив A текущий номер 3 элемента массива С 3 раза
5) 3 3 3 5 3 7 7 3 5 5 - записываем в массив A текущий номер 4 элемента массива С 0 раз
6) 3 3 3 5 5 5 5 3 5 5 - записываем в массив A текущий номер 5 элемента массива С 4 раза
7) 3 3 3 5 5 5 5 3 5 5 - записываем в массив A текущий номер 6 элемента массива С 0 раз
8) 3 3 3 5 5 5 5 7 7 7 - записываем в массив A текущий номер 7 элемента массива С 3 раза
МАССИВ ОТСОРТИРОВАН!
Vasiliy Ganov
(950)
незачто, обращайтесь 🙂