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

Метод прямого включения

DO (i: = 2, 3, … n)

t: = a_i, j: =i-1

DO (j > 0 и t < a_j)

a_j+1:= a_j

j: = j-1

OD

a_j+1:= t

OD

Для метода прямого включения справедливы следующие оценки величин М и С.

C_min £ С_сред £ C_max, где C_min = n-1, C_max = ,

М_min £ М_сред £ М_max, где М_min = 2(n-1), M_max = .

Минимальные и максимальные значения величин С и М достигаются на прямо отсортированном и обратно отсортированном массивах соответственно. Таким образом, средняя трудоемкость этого метода имеет квадратичный порядок, т.е. С = О(n²) М = О(n²), при n®¥.

Метод прямого включения устойчивый.

3.2 Метод Шелла

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

Предварительное упорядочивание будем проводить с помощью k – сортировок. Суть k – сортировки заключается в следующем. Массив разбивается на последовательности с шагом k

a_i, a_k+i, a_2k+i, …,a_[n/k]k+i, i = 1, 2,…,k

и сортировка происходит только внутри этих последовательностей.

Обозначим через H последовательность из m возрастающих шагов

H=(h₁, h₂, … h_m), где h₁=1, h₁ < h₂ < h₃ < … < h_m

Метод Шелла состоит в последовательном проведении h_i-сортировки, i=m, m-1,…, 1, причем h₁=1 гарантирует, что массив будет полностью отсортирован, поскольку 1-сортировка является методом прямого включения.

Пример.Отсортировать слово методом Шелла. Последовательность шагов выберем следующим образом h₁=1, h₂=2.

2-сортировка

К	У	Р	А	П	О	В	А
К	У	Р	А	П	О	В	А
К	А	Р	У	П	О	В	А
К	А	П	У	Р	О	В	А
К	А	П	О	Р	У	В	А
В	А	К	О	П	У	Р	А
В	А	К	А	П	О	Р	У

1-сортировка

Рисунок 6 Метод Шелла