Сортировка Шелла.

Данный метод разработан американским ученым в области информатики Дональдом Шеллом. Метод сортировки Shellsort был назван в честь него. Сортировка Шелла базируется на методе сортировки вставками. При неудачном наборе данных может выйти так, что несколько наименьших элементов массива окажутся последними, тогда как массив уже почти полностью отсортирован. В этом случае нам придется сравнивать их почти со всеми элементами массива. Конечно, такого хотелось бы избежать. В методе Шелла выполняется сравнение нескольких элементов, находящихся на заданном расстоянии друг от друга. Сначала этих элементов для сравнения несколько. Затем величина этого интервала постепенно сокращается, увеличивается количество элементов для сравнения, но и элементы массива уже оказываются почти упорядочены. На последнем этапе можно выполнить обычную сортировку вставкой, которая очень эффективна на почти отсортированных данных.

shellSort

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

Возможно, что у вас уже возник вопрос: а как собственно выбрать величину этого интервала? Исходя из чего делать этот выбор. На самом деле ответ на этот вопрос не так прост. В своей книги Искусство программирования т.3, посвященной сортировке, Д.Кнут предлагает следующую формулу:

h = 3*h + 1, где

h — величина интервала.

Исходное значение h можно определить, выполнив данную операцию в цикле до превышения значения размера массива.

Таким образом, мы получим начальное значения для выполнения действий. На каждой итерации величина интервала будет сокращаться. Определить новое значение h на каждом шаге можно по обратной формуле:

h = (h — 1)/3

Реализация алгоритма на языке Java:

На каждом этапе мы сравниваем элементы, находящиеся на расстоянии h, постепенно сдвигаясь вправо. При необходимости меняем элементы местами.

Реализация алгоритма на языке C:

За счет того, что перед последним этапом массив частично отсортирован, мы получаем значительный прирост в скорости и алгоритм выполняется за время O(N(logN)^2).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *