Описание. При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d (о выборе значения d см

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

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

● отсутствие потребности в памяти под стек;

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

История

Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году. В некоторых старых пособиях этот алгоритм назывался Сортировка Шелл-Мецнер, в честь Марлен Мецнер-Нортон[ источник не указан 366 дней ]. Однако, впоследствии, сама Мецнер опровергла это: «Я не имею ничего общего с этой сортировкой, и моё имя никогда не должно связываться с ней»[ источник не указан 366 дней ].

Пример

Пусть дан список A = (32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5, 3, 1.

На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A 5, 1 = (32, 66, 40), A 5, 2 = (95, 35, 43), A 5, 3 = (16, 19, 93), A 5, 4 = (82, 75, 68), A 5, 5 = (24, 54).

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Процесс завершается обычной сортировкой вставками получившегося списка.