Написать сортировку
Шелла N чисел со следующим шагом приращений (последовательность Седжвика, элементы берутся в обратном порядке): 1,19,41,109,209,505,929,2161,3905,8929,16001,36289,64769...
В этой последовательности используются только первые k членов - inc[0], inc[1], ..., inc[k-1], где
k - наименьшее число, при котором 3*inc[k]>N.
Число элементов
массива N вводится с клавиатуры.
Входные данные
В
первой строке записано натуральное число N (N <=
50 000).
В последующих строках содержится N целых чисел из отрезка
[0, 1 000 000 ]. Числа разделены пробелами и/или символами конца строки.
Выход
Программа должна записать в выходной поток натуральное число р, где р – число перестановок,
совершаемое при сортировке входных данных.
Примеры входных и выходных данных
INPUT OUTPUT
5 8
23 54 17 0 9
8 12
65 12 76 32 68 21 90 44
Автор: Маклаков Г.В.
