Loading AI tools
алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками Из Википедии, свободной энциклопедии
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
Сортировка Шелла | |
---|---|
![]() Сортировка с шагами 23, 10, 4, 1. | |
Автор | Дональд Шелл[1] |
Предназначение | Алгоритм сортировки |
Структура данных | Массив |
Худшее время | |
Лучшее время | |
Среднее время | зависит от выбранных шагов |
Затраты памяти | всего, дополнительно |
При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.
Пусть дан список и выполняется его сортировка методом Шелла, а в качестве значений выбраны .
На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:
template<typename RandomAccessIterator, typename Compare>
void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )
{
for( auto d = ( last - first ) / 2; d != 0; d /= 2 )
//нужен цикл для first = a[0..d-1]
for( auto i = first + d; i != last; ++i )
for( auto j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )
std::swap( *j, *( j - d ) );
}
void shell_sort(int *array, int size) {
for (int s = size / 2; s > 0; s /= 2) {
for (int i = s; i < size; ++i) {
for (int j = i - s; j >= 0 && array[j] > array[j + s]; j -= s) {
int temp = array[j];
array[j] = array[j + s];
array[j + s] = temp;
}
}
}
}
void shell_sort(List<Integer> array) {
for (int s = array.size() / 2; s > 0; s /= 2)
for (int i = s; i < array.size(); ++i)
for (int j = i - s; j >= 0 && array.get(j) > array.get(j + s); j -= s) Collections.swap(array, j, j + s);
}
def shell_sort(data: list[int]) -> list[int]:
last_index = len(data)
step = len(data)//2
while step > 0:
for i in range(step, last_index, 1):
j = i
delta = j - step
while delta >= 0 and data[delta] > data[j]:
data[delta], data[j] = data[j], data[delta]
j = delta
delta = j - step
step //= 2
return data