Метод квадратичного выбора (Э.Х. Фрэнд)

[Figushkin]

Метод квадратичного выбора (Э.Х. Фрэнд). Пусть N является точным квадратом натурального числа, например 3. Разделим массив на Sqrt(N) групп. Выберем максимальный элемент в каждой группе... Проще рассмотреть пример. Дан массив 7 10 3 5 15 9 6 12 8. При разбивке на группы – (7 10 3) (5 15 9) (6 12 8) . Максимальные элементы 10 15 12. Максимальный из них 15. он во второй группе. Если оставшиеся элементы из второй группы, а это 5 и 9, меньше 10 и 12, то мы нашли сразу три элемента, записываемые на свои места. Если нет, то заменяем максимальные элементы элементами из группы. По данному алгоритму отсортировать массив по возрастанию элементов.