Теоретические сведения. Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками

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

Метод Шелла является усовершенствованием метода простого включения, который основан на том, что включение использует любой частичный порядок. Но недостатком простого включения является то, что во внутреннем цикле элемент A[i] фактически сдвигается на одну позицию. И так до тех пор, пока он не достигнет своего места в отсортированной части. (На самом деле передвигалось место, оставленное под A[i]). Метод Шелла позволяет преодолеть это ограничение следующим интересным способом.
Вместо включения A[i] в подмассив предшествующих ему элементов, его включают в подсписок, содержащий элементы A[i – h], A[i – 2h], A[i – 3h] и так далее, где h – положительная константа. Таким образом, формируется массив, в котором «h-серии» элементов, отстоящие друг от друга на h, сортируются отдельно. Конечно, этого недостаточно: процесс возобновляется с новым значением h, меньшим предыдущего. И так до тех пор, пока не будет достигнуто значение h = 1.

Пример сотрировки методом Шелла приведен на рис.1

Рис.1. Сортировка методом Шелла

Блок-схема алгоритма сортировки методом Шелла представлена на рис.2

Рис.2. Алгоритм сортировки методом Шелла

Реализация сортировки методом Шелла на языке С

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

2. Постановка задачи:

Отсортировать одномерный и двумерный массивы методом Шелла по возрастанию.

Массивы сгенероровать с помощью генератора случайных чисел, вывести на печать.