Метод Шелла

Метод вставки

Метод отбора

При сортировке методом отбора алгоритм находит элемент с наименьшим значением и выполняет перестановку, меняя его с первым элементом массива. Из оставшихся (n-1) элементов находят 2 минимальный элемент.

Продолжение программы:

// Метод отбора.

int exchange, ind; // ind-индекс минимального элемента.

// exchange-перестановка.

for (i=0; i<n-1; i++)

{ exchange=0;

ind=i

prom=b[i]; // Сохраняем i-элемент массива.

for (j=i+1; j<n; j++)

if ( b[j]<prom )

{ ind=j;

prom=b[j]; // Минимальное значение ячейки.

exchange=1; // Делаем перестановку.

}

if (exchange)

{ b[ind]=b[i];

b[i]=prom;

}

}

. . . . .} Печать

Сортировка методом отбора – n-квадратичный алгоритм и требует

сравнений.

Количество перестановок:

Наилучший случай: 3*(n-1)

Наихудший случай:

Средний случай: n*(logn+y), где y-константа Эйлера y»0.577216.

Т.е. показатель количества перестановок в среднем случае выше, чем в пузырьковом методе.

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

Продолжение программы.

// Метод вставки.

for (i=1; i<n; i++)

{ prom=c[i];

for (j=i-1; j>=0 && prom<c[j]; j--)

c[j+1]=c[j];

c[j+1]=prom;

}

. . . .}печать.

В отличие от пузырьковой сортировки и сортировки методом отбора количество сравнений зависит от исходной упорядоченности списка. Если список отсортирован в нужном порядке, то количество сравнений = (n-1), если список неупорядочен, то количество сравнений = .

Количество перестановок:

В наилучшем случае: 2*(n-1)

В среднем случае:

В наихудшем случае:

Метод вставки обладает двумя преимуществами:

1) его поведение естественно, и если массив уже отсортирован в нужном порядке, то алгоритм производит наименьшее количество вычислений.

2) Этот метод не изменяет порядка следования одинаковых элементов (ключей).

Все эти алгоритмы имеют общий недостаток: время выполнения алгоритма.

При достижении некоторой критической точки все эти алгоритмы становятся

недопустимо медленными.

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

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

Продолжение программы

// Метод Шелла

int g[5];

int k, p;

g[0]=9; g[1]=5; g[2]=3; g[3]=2; g[4]=1;

for (k=0; k<5; k++)

{ p=g[k];

for (i=p; i<n; ++i)

{ prom=d[i];

for (j=i-p; prom<d[j] && j>=0; j=j-p)

d[j+p]=d[j];

d[j+p]=prom;

}

}

. . . .}печать

} // end for