Метод Шелла

Метод Шелла (Shell D.L., 1959) - метод сортування вставками (включеннями) з відстанями, що зменшуються.

Візьмемо для прикладу масив:

На першому етапі масив уявно ділиться на підмасиви з елементами, що, скажімо, відстоять один від одного на 4 елементи:

1.

2.

3.

4.

Кожен з них впорядковується окремо:

1.

2.

3.

4.

Сортування робиться у кожному підмасиві вставками (методом простого включення).

На другому етапі підмасиви утворюються елементами через один:

1.

2.

Одержуємо

1.

2.

Після цього весь масив сортується разом. За рахунок попередніх етапів він виявляється вже близьким до відсортованого, тому обмінів необхідно вже не так багато.

Аналіз та експериментальні дослідження методу показують, що цей метод дає кращі результати, якщо розподіл на підмасиви роблять кроками, що не є степенями двійки, а, навпаки, не є множниками один одного.

Рекомендованими є такі послідовності кроків:

У останньому випадку кількість необхідних операцій пропорційна n^6/5 = n^1,2.