Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
25.
Основная идея алгоритма Шелла:
Выберем некоторое целое число h и разобьем исходный массив на подмассивы:
первый подмассив содержит элементы k(0), k(h), k(2h), ...;
второй подмассив содержит элементы k(1), k(1 + h), k(1 + 2h), ...;
. . .
h-й подмассив содержит элементы k(h – 1), k(2h – 1), k(3h – 1), ... .
Таких подмассивов будет h, и каждый из этих подмассивов упорядочивается методом простых вставок. После того, как все подмассивы будут упорядочены, выберем новое значение h, меньшее предыдущего, и повторим процесс разбиения и сортировки. Процесс повторяется столько раз, сколько задано значений h. Последнее значение h всегда выбирается равным 1, т.е. сортируется один подмассив, состоящий изо всех элементов исходного массива. Это гарантирует получение отсортированного массива. Определение 1. Назовем h-сортировкой массива сортировку h его подмассивов: k(0), k(0 + h), k(0 + 2h), ... k(1), k(1 + h), k(1 + 2h), ... ... k(h – 1), k(2h – 1), k(3h – 1), ... . Зададим последовательность шагов ht > ht-1 > … > h1 = 1. Тогда алгоритм Шелла состоит из ht-сортировки, за которой следует ht-1-сортировка и т.д. Определение 2. Массив, в котором k(i) ≤ k(i + h) для 0 ≤ i < n – h, будем называть h-упорядоченным. Так как первый шаг ht большой, отдельные подмассивы достаточно малы по размеру, поэтому сортировка простыми вставками этих подмассивов выполняется быстро. Сортировка отдельных подмассивов приводит к тому, что число инверсий в массиве в целом уменьшается. Последующие этапы используют большие по размеру подмассивы, содержащие меньшее число инверсий. Поэтому сортировка простыми вставками этих подмассивов также достаточно эффективна. Это – интуитивное объяснение того факта, что алгоритм Шелла эффективнее более простых вариантов сортировки вставками. Формальный анализ этого алгоритма сложен, т.к. вычислительная сложность его работы на i-ом шаге существенно зависит от результатов предыдущих шагов. До сих пор не удалось найти наилучшую последовательность шагов ht-1, ht-2, ..., h1. Известны выражения для вычислительной сложности лишь для некоторых частных случаев последовательностей шагов. Рассмотрим пример: Отсортировать методом Шелла массив k[i] 44 55 12 42 94 18 6 67 70 9 3 97 34 20 25 с последовательностью шагов h1=1, h2=4, h3=7. 1) h3=7. Исходный массив разбивается на следующие подмассивы (число подмассивов равно 7) 1: {k[0]=44; k[7]= 67;k[14]=25} 2: {k[1]=55; k[8]=70} 3: {k[2]=12; k[9]=9} 4: {k[3]=42; k[10]=3} 5: {k[4]=94; k[11]=97} 6: {k[5]=18; k[12]=34} 7: {k[6]=6; k[13]=20}
Каждый из этих подмассивов упорядочим методом простых вставок. Получаем следующий массив:
|
k[i] |
25 |
55 |
9 |
3 |
94 |
18 |
6 |
44 |
70 |
12 |
42 |
97 |
34 |
20 |
67 |
2) h2=4. Массив, получившийся после 1), разбивается на следующие подмассивы (число подмассивов равно 4)
1: {k[0]=25; k[4]=94; k[8]=70; k[12]=34}
2: {k[1]=55; k[5]=18; k[9]=12; k[13]=20}
3: {k[2]=9; k[6]=6; k[10]=42; k[14]=67}
4: {k[3]=3; k[7]=44; k[11]=97}
Каждый из этих подмассивов упорядочим методом простых вставок. Получаем следующий массив:
|
k[i] |
25 |
12 |
6 |
3 |
34 |
18 |
9 |
44 |
70 |
20 |
42 |
97 |
94 |
55 |
67 |
3) h1=1. Подмассив один, состоящий из полного массива, получившегося после 2):
1: {25, 12, 6, 3, 34, 18, 9, 44, 70, 20, 42, 97, 94, 55 ,67}
Отсортируем его методом простых вставок. Получаем отсортированный массив:
|
k[i] |
3 |
6 |
9 |
12 |
18 |
20 |
25 |
34 |
42 |
44 |
55 |
67 |
70 |
94 |
97 |
Реализация на языке С++ алгоритма Шелла сортировки вставками с убывающим шагом n записей типа T, находящихся в массиве k, для хранящейся в массиве h последовательности t шагов n/2 ≥ ht-1 > ht-2 > ... > h1 > h0 = 1, представлена в листинге 2. Комментарии в правой части листинга содержат число выполнений соответствующей строки в алгоритме и поясняют определение его вычислительной сложности. В формулах через ur,i обозначено (при заданном шаге hr) число записей k(j), j = i – hr, i – 2hr, ..., которые больше записи k(i), то есть составляют с ней инверсию.
Листинг 2. Алгоритм Шелла
template <typename T>
void SortShell(T * k, int n, int * h, int t) {
T temp;
for (int r = t-1; r >= 0; --r) // t
for (int i = h[r]; i < n; ++i) { // n – h[r]
temp = k[i]; // n – h[r]
int j = i - h[r];
while (j > -1 && k[j] > temp) {
k[j + h[r]] = k[j];
j -= h[r];
}
k[j + h[r]] = temp; // n – h[r]
}
}
Вычислительная сложность алгоритма
Вычислительная сложность алгоритма Шелла равна
где A(t), B(t) и C(t) – функции, значения которых зависят от числа шагов t и их значений.
Очевидно, что минимум вычислительной сложности достигается на упорядоченном массиве: