Сортировка методом Шелла кратко

Привет, сегодня поговорим про сортировка шелла, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка шелла , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

В 1959 году американский ученый Дональд Шелл опубликовал алгоритм сортировки, который впоследствии получил его имя – « сортировка шелла ». Этот алгоритм может рассматриваться и как обобщение пузырьковой сортировки, так и сортировки вставками.

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определенном расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расческой.

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.

Далее, на примере последовательности целых чисел, показан процесс сортировки массива методом Шелла. Для удобства и наглядности, элементы одной группы выделены одинаковым цветом.

Первое значение, соответствующее расстоянию d равно 10/2=5. На каждом шаге оно уменьшается вдвое. Элементы, входящие в одну группу, сравниваются и если значение какого-либо элемента, стоящего левее того с которым он сравнивается, оказывается больше (сортировка по возрастанию), тогда они меняются местами. Так, элементы путем внутригрупповых перестановок постепенно становятся на свои позиции, и на последнем шаге (d=1) сортировка сводится к проходу по одной группе, включающей в себя все N элементов массива. При этом число требуемых обменов оказывается совсем небольшим.

Код программы на C++:

Код программы на Pascal:

Реализация на C++

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 ) );
}

Реализация на C

void ShellSort (int array[], int size)               // * ∆k = (b∆k−1)/2  ∆0 = N
{
	int step, i, j, tmp;
	
	// Выбор шага
	for (step = size / 2; step > 0; step /= 2)
	    // Перечисление элементов, которые сортируются на определенном шаге
		for (i = step; i < size; i++) 
		    // Перестановка элементов внутри подсписка, пока i-тый не будет отсортирован
			for (j = i - step; j >= 0 && array[j] > array[j + step]; j -= step)
			{
				tmp = array[j];
				array[j] = array[j + step];
				array[j + step] = tmp;
			}
}

Реализация на Java

for (int step = n / 2; step > 0; step /= 2) {
    for (int i = step; i < n; i++) {
        for (int j = i - step; j >= 0 && a[j] > a[j + step] ; j -= step) {
            int x = a[j];
            a[j] = a[j + step];
            a[j + step] = x;
        }
    }
}

Реализация на Python

def shell_sort(data: List[int]) -> List[int]:
    last_index = len(data) - 1
    step = len(data)//2
    while step > 0:
        for i in range(last_index):
            j = i + step
            if j > last_index:
                break
            if data[i] > data[j]:
                data[i], data[j] = data[j], data[i]
        step //= 2
    return data

Сортировка Шелла уступает в эффективности быстрой сортировки, но выигрывает у сортировки вставками. Об этом говорит сайт https://intellect.icu . Сравнить скорость работы этих трех алгоритмов можно, воспользовавшись следующей таблицей.

Вау!! 😲 Ты еще не читал? Это зря!:

• Шейкерная сортировка (перемешиванием) .
• Сортировка слиянием .
• Сортировка пузырьком.
• Быстрая сортировка .
• Сортировка выбором.

На этом все! Теперь вы знаете все про сортировка шелла, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка шелла и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов