Алгоритм на псевдокоде. Сортировка методом Шелла

2 3 4 5 6 7 8

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

DO (k=h_m, h_m_-1, … 1)

DO (i=k+1, k+2, … n)

t: = a_i, j: =i-k

DO (j>0 и t < a_j)

a_j+k: = a_j

j: = j-k

a_j+k: = t

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

h₁=1, h_i=2h_i_-1+1, i=2,… m, m=

При такой последовательности шагов средний порядок трудоёмкости O(n^1.2), n → ∞. Таким образом, метод Шелла существенно быстрее методов с квадратичной трудоемкостью. Метод Шелла не устойчив.

3.3 Варианты заданий

1. Разработать процедуру сортировки массива целых чисел методом прямого включения (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.

2. Разработать процедуру сортировки массива целых чисел методом Шелла (язык программирования Паскаль или Си). Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве. Предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.

3. Сравнить метод прямого включения и метод Шелла по количеству сравнений и пересылок для различных типов массивов. Разработать процедуру построения графика зависимости величин М и С от размера массива.

4. Сравнить метод прямого включения и метод Шелла с ранее расмотренными методами сортировки по количеству сравнений и пересылок для различных типов массивов. Разработать процедуру построения графика зависимости величин М и С от размера массива

5. Экспериментально определить подходящую последовательность шагов для метода Шелла.

6. Опытным путем определить константы в выражениях оценки для количества сравнений и пересылок в методе Шелла.

4. Быстрые методы сортировки массивов

4.1 Пирамидальная сортировка

Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность a_i, a_i₊₁,…,a_k называется (i,k)-пирамидой, если неравенство

a_j≤min(a₂_j, а₂_j₊₁) (*)

выполняется для каждого j, j=i,…,k для которого хотя бы один из элементов a₂_j, a₂_j₊₁ существует.

Например, массив А является пирамидой, а массив В ¾ не является.

А=(а₂, а₃, а₄, а₅, а₆а₇, а₈)=(3, 2, 6, 4, 5, 7)

В=(b₁, b₂, b₃, b₄, b₅, b₆, b₇)=(3, 2, 6, 4, 5, 7)