Сортировка вставками

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

Начало d c a b

Проход 1 c d a b

Проход 2 a c d b

Проход 3 a b c d

Пример реализации сортировки вставками показан ниже:

/* Сортировка вставками. */

void insert(char *items, int count)

{

register int a, b;

char t;

for(a=1; a < count; ++a) {

t = items[a];

for(b=a-1; (b >= 0) && (t < items[b]); b--)

items[b+1] = items[b];

items[b+1] = t;

}

}

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

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

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

Сортировка шелла

Сортировка Шелла называется так по имени своего автора, Дональда Л. Шелла (Donald Lewis Shell). Однако это название закрепилось, вероятно, также потому, что действие этого метода часто иллюстрируется рядами морских раковин, перекрывающих друг друга (по-английски "shell" — "раковина"). Общая идея заимствована из сортировки вставками и основывается на уменьшении шагов. Рассмотрим диаграмму на рис. 21.2. Сначала сортируются все элементы, отстоящие друг от друга на три позиции. Затем сортируются элементы, расположенные на расстоянии двух позиций. Наконец, сортируются все соседние элементы.

Проход 1 f d a c b e

\___\___\___/ / /

\___\_____/ /

\_______/

Проход 2 c b a f d e

\___\___|___|___/ /

\______|______/

Проход 3 a b c d e f

|___|___|___|___|___|

Результат a b c d e f

Рис. 21.2. Сортировка Шелла

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

Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность:

9, 5, 3, 2, 1

дает хорошие результаты и применяется в показанной здесь реализации сортировки Шелла. Следует избегать последовательностей, которые являются степенями числа 2 — по математически сложным соображениям они уменьшают эффективность сортировки (но сортировка по-прежнему работает!).

/* Сортировка Шелла. */

void shell(char *items, int count)

{

register int i, j, gap, k;

char x, a[5];

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

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

gap = a[k];

for(i=gap; i < count; ++i) {

x = items[i];

for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)

items[j+gap] = items[j];

items[j+gap] = x;

}

}

}

Вы могли заметить, что внутренний цикл forимеет два условия проверки. Очевидно, что сравнениеx<items[j]необходимо для процесса сортировки. Выражениеj>=0предотвращает выход за границу массиваitems. Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.

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

Анализ сортировки Шелла связан с очень сложными математическими задачами, которые выходят далеко за рамки этой книги. Примите на веру, что время сортировки пропорционально n^1,2при сортировкеnэлементов. А это уже существенное улучшение по сравнению с сортировками порядкаn². Чтобы понять, насколько оно велико, обратитесь к рис. 21.3, на котором показаны графики функцийn²иn^1,2. Тем не менее, не стоит чрезмерно восхищаться сортировкой Шелла — быстрая сортировка еще лучше.

Рис. 21.3. Попытка наглядного представления кривых n² и n^1,2. Хотя вычертить эти кривые с точным соблюдением масштаба на каком-нибудь значимом для целей сортировки интервале изменения количества записей (n), например, на интервале от 0 до 1000, не представляется возможным, получить представление о поведении этих кривых можно с помощью графиков функций у=(n/100)² и у=(n/100)^1,2. Для сравнения построен также график прямой у=n/100. Кроме того, чтобы получить представление о росте этих кривых, можно на оси ординат принять логарифмический масштаб, — это все равно, что начертить логарифмы этих функций