Метод Шелла

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

• отсутствие потребности в памяти под стек;
• отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

n=length(x);

b=round(n/2);

while b >= 1

for I=1:n

if (I+b<=n) && (x(I) > x(I+b))

zam=x(I); x(I)=x(I+b); x(I+b)=zam;

end

end

I=0;

if round(b) > 1;

b=round(b/2);

else

b=b/2;

end

end

x

Вывод: Существует множество методов сортировки которые можно реализовать в системе MathLab. Судя по проведённому сравнению методов сортировке наиболее быстром оказался метод используемый во встроенной в систему функции sort, наиболее близким к нему оказалась сортировка выполненная по методу Шелла. Далее шли методы в таком порядке:

1) Метод выборки на месте.

2) Метода вставки.

3) Метод Челночка.

4) Метод пузырька.