Сортировка Шелла | |
---|---|
Сортировка с шагами 23, 10, 4, 1. | |
Предназначение | Алгоритм сортировки |
Структура данных | Массив |
Худшее время | O(n2) |
Лучшее время | O(n log2 n) |
Среднее время | зависит от выбранных шагов |
Затраты памяти | О(n) всего, O(1) дополнительно |
Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.
При сортировке Шелла сначала сравниваются и сортируются между собой значения, стоящие один от другого на некотором расстоянии (о выборе значения см. ниже). После этого процедура повторяется для некоторых меньших значений , а завершается сортировка Шелла упорядочиванием элементов при (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
Сортировка Шелла была названа в честь её изобретателя — Дональда Шелла, который опубликовал этот алгоритм в 1959 году.
Пусть дан список
и выполняется его сортировка методом Шелла, а в качестве значений
выбраны
.
На первом шаге сортируются подсписки , составленные из всех элементов , различающихся на 5 позиций, то есть подсписки , , , , .
В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.
Процесс завершается обычной сортировкой вставками получившегося списка.
Среднее время работы алгоритма зависит от длин промежутков — , на которых будут находиться сортируемые элементы исходного массива ёмкостью на каждом шаге алгоритма. Существует несколько подходов к выбору этих значений:
template< typename RandomAccessIterator, typename Compare >
void shell_sort( RandomAccessIterator first, RandomAccessIterator last, Compare comp )
{
for( typename std::iterator_traits< RandomAccessIterator >::difference_type d = ( last - first ) / 2; d != 0; d /= 2 )
for( RandomAccessIterator i = first + d; i != last; ++i )
for( RandomAccessIterator j = i; j - first >= d && comp( *j, *( j - d ) ); j -= d )
std::swap( *j, *( j - d ) );
}
// BaseType - любой перечисляемый тип
// typedef int BaseType - пример
void ShellsSort(BaseType *A, unsigned N)
{
unsigned i, j, k;
BaseType t;
for(k = N / 2; k > 0; k /= 2)
for(i = k; i < N; i++)
{
t = A[i];
for(j = i; j >= k; j -= k)
{
if(t < A[j - k])
A[j] = A[j - k];
else
break;
}
A[j] = t;
}
}
public class ShellSort {
public void sort (int[] arr) {
int increment = arr.length / 2;
while (increment >= 1) {
for (int startIndex = 0; startIndex < increment; startIndex++) {
insertionSort(arr, startIndex, increment);
}
increment = increment / 2;
}
}
private void insertionSort (int[] arr, int startIndex, int increment) {
for (int i = startIndex; i < arr.length - 1; i = i + increment) {
for (int j = Math.min(i + increment, arr.length - 1); j - increment >= 0; j = j - increment) {
if (arr[j - increment] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - increment];
arr[j - increment] = tmp;
} else {
break;
}
}
}
}
}
def shellSort(array):
increment = len(array) // 2
while increment > 0:
for startPosition in range(increment):
gapInsertionSort(array, startPosition, increment)
print("После инкрементации размера на", increment,"массив:", array)
increment //= 2
def gapInsertionSort(array, low, gap):
for i in range(low + gap, len(array), gap):
currentvalue = array[i]
position = i
while position >= gap and array[position - gap] > currentvalue:
array[position] = array[position - gap]
position = position - gap
array[position] = currentvalue
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .