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

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской».

Как известно, вставочный метод очень эффективно обрабатывает почти отсортированные массивы. Сортировка Шелла при первоначальных проходах достаточно быстро доводит массив к состоянию неполной упорядоченности. На заключительном этапе шаг равен единице, т.е. «Шелл» естественным образом трансформируется в сортировку простыми вставками.

Алгоритм сортировки

Идея сортировки методом Шелла состоит в том, чтобы сортировать элементы отстоящие друг от друга на некотором расстоянии step. Затем сортировка повторяется при меньших значениях step, и в конце процесс сортировки Шелла завершается при step = 1 (а именно обычной сортировкой вставками).

До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Первоначально автор сортировки, Дональд Шелл, предложил ряд

$$[n/2], [n/4], [n/8], ..., 1$$

который давал скорость $$\mathcal{O}(n^2)$$.В течении последующих 50 лет, многие исследователи (среди которых — легендарный Роберт Седжвик) подбирали различные зависимости, постепенно улучшая результат. На данный момент таковым является ряд, предложенный в 2001 году Марсином Сиурой:

701, 301, 132, 57, 23, 10, 4, 1.

Это — результат многочисленных тестов, до сих пор неизвестно, можно или нельзя его улучшить.

Визуализация работы алгоритма

Реализация алгоритма

static void ShellSort(int[] arr)
{
    int j;
    int step = arr.Length / 2;

    while (step > 0)
    {
        for (int i = 0; i < (arr.Length - step); i++)
        {
            j = i;
            while((j >= 0) && (arr[j] > arr[j + step]))
            {
                int temp = arr[j];
                arr[j] = arr[j + step];
                arr[j + step] = temp;
                j -= step;
            }
        }
        step /= 2;
    }
}

Характеристики алгоритма