Razdatochnye_materialy_chast_1

1

0

1

Специальные случаи сортировки

Задача: отсортировать массив целых чисел при

условии, что каждое число может встретиться в

массиве не более одного раза.

Алгоритм (без единого сравнения): пусть целое число

занимает 2 байта, и его максимальное значение есть

65435. Создадим символьный массив размером

65435, заполненный нулями (назовём его таблицей).

Просмотрим сортируемый массив, и встречая там

какое-либо число, соответствующий элемент

таблицы устанавливаем в 1. Потом, просматривая

таблицу от младших индексов к старшим,

формируем отсортированный массив.