Сортировка с убывающим шагом

Сортировка с убывающим шагом

Сортировка с убывающим шагом Бьём массив на N/pow(2,log2(N)-i) групп по N/pow(2,i). Расстояние между элементами в группе равно pow(2,log2(N)-i). Каждую из групп отсортируем по возрастанию. i++. При сортировке каждой отдельно взятой группы можно пользоваться методом простых вставок. В произвольном массиве разбивка на группы элементов производится так, чтобы в каждую группу входило не более двух элементов. Шаг между элемен­тами группы может быть степенью числа 2 (т. е. 8, 4, 2,1), но может быть и дру­гим (например, 7, 5, 3, 1). Процесс завершается, когда расстояние между элементами в группе станет равным единице. Основная идея - перестановки элементов выполняются не на одну пози­цию, а сразу на несколько - скачками. Самый большой скачок на N/2 элементов Оценка метода: - Количество сравнений примерно равно pow(N,3/2)/2.

Связать^?