Сортировка по методу Шелла также относится к обменным сортировкам, и даже принцип функционирования очень похож на "метод пузырька".

В этом методе первоначально рассматриваются элементы отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива.

На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка")

Давайте рассмотрим пример:

Дано множество
{6,3,4,8,2,9}
 d=[n/2]=[6/2]=3

{6,3,4,8,2,9} - сравниваем 6 и 8
{6,2,4,8,3,9} - сравниваем 3 и 2, переставляем
{6,3,4,8,2,9} - сравниваем 4 и 9

далее d=[d/2]=[3/2]=1
выродился в метод "Пузырька"

В этом примере не очень видна эффективность этого метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие.

#include <stdio.h>
#include <stdlib.h>

int BubbleSort(int *array,int len)
{
	/* Код сортировки из предыдущего шага */
};

int ShellSort(int *array,int len)
{
	long d=len,i,j;
	int c;

	do
	{
		d=d/2;
		i=0;
		while ((j=i+d)<len)
		{
			if (array[i]>array[j])
			{
				c=array[i];
				array[i]=array[j];
				array[j]=c;
			};
			i++;
		};
	}
	while (d>1);

	BubbleSort(array,len);
};

int main()
{
	int k[10]={8,-5,1,7,3,-10,6,5,10,9};
	printf("\n\n\n");
	for (int i=0; i<10;i++)
		printf(" %d ",k[i]);
	printf("\n");

	ShellSort(k,10);

	for (i=0; i<10;i++)
		printf(" %d ",k[i]);
	printf("\n");

	return 0;
};

Результат выполнения:

 8  -5  1  7  3  -10  6  5  10  9
 -10  -5  1  3  5  6  7  8  9  10

Для теста эффективности я создал счетчик циклов, и до вырождения в метод "Пузырька" было выполнено всего 3 прохода. Причем, что больше всего меня удивило, массив был вот в каком состоянии:

 -10  -5  1  3  5  6  7  8  9  10

А тут видно, что он уже отсортирован и метод "Пузырька" работал в холостую, но совершил всего один цикл, т.к. в нем выполнилось условие Айверсона.

Помоему очевидно, что метод Шелла обладает большим быстродействием.