Сортировка методом Шелла

Сортировка методом Шелла

Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.
Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i – h], A[i – 2h], A[i – 3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h-серии» элементов, отстоящие друг от друга на h, сортируются отдельно. Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h = 1.

Блок схема алгоритма Шелла

Реализация алгоритма Шелла на С++

01	//метод Шелла

02	void sort_Shell(int *mas,int n)

03

{

04	int i,j; //"бегунки"

05	int temp; //вспомогательная переменна

06	int h = n/2;

07	while(h>0)// проверяем, если h>0 то входим в тело цикла

08

{

09	for(i=0;i=0)

10

{

11	if(mas[j] > mas[j+h])

12

{

13	temp = mas[j];

14	mas[j] = mas[j+h];

15	mas[j+h] = temp;  //перестановка элементов

16

j=j-h;

17

}

18

else

19	j=-1;// перестановки не было -  "бегунок" уменьшим на 1

20

}

21

}

22

h=h/2;

23

}

24

}

25	/******************/

Вывод по алгоритму Шелла

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n^1.25), для худшего случая оценкой является O(n^1.5). Также следует сказать, что дополнительной памяти данный алгоритм не требует, но и не гарантирует сохранение порядка элементов с одинаковыми значениями.