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

В этом уроке будет рассмотрена сортировка Шелла. Мы приведем алгоритм, а также его реализацию на языке программирования Си с подробными комментариями.

Описание алгоритма “Сортировка Шелла”

Этот метод сортировки Д. Шелл предложил в 1959 г. Он использует минимум памяти и показывает высокие скорости при сортировке. По сути в методе Шелла применяются сравнения и перестановки элементов аналогичные методу вставок, но при этом порядок сравниваемых элементов совершенно другой.

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

До сих пор продолжает обсуждаться вопрос выбора шага сортировки step. Шелл предложил такую последовательность: N/2, N/4, N/8 …, где N – количество элементов в сортируемом массиве.

Сортировка Шелла требует около log2N проходов для упорядочивания последовательности длиной N.

Реализация алгоритма сортировки Шелла

Ниже приводится программная реализация на языке программирования Си:

где n – количество элементов в массиве, а mass[] – упорядочиваемый массив элементов.

Пример программы

Ниже мы приводим пример консольной программы с подробными комментариями, которая считывает массив целых чисел из N элементов, сортирует его методом Шелла и выводит результат сортировки на экран. В конце статьи вы можете скачать исходник этой программы, написанной в Visual Studio на языке Си.

Демонстрация работы программы:

Сортировка Шелла. Демонстрация работы программы

 

Скачать исходник

 

 

Сортировка Шелла
5 (100%) 2 votes

Поделиться в соц. сетях:

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

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

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">