2.1. Сортировка с помощью вставок

Элементы мысленно делятся на уже "готовую" последовательность a₁, ..., a_i-1 и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и переносится в готовую последовательность, при этом он вставляется на нужное место. В табл. 4.1 показан в качестве примера процесс сортировки с помощью вставки восьми случайно выбранных чисел.

Таблица 5.1.

Начальные ключи 44 55 12 42 94 18 06 67

i=2 44 55 12 42 94 18 06 67

i=3 12 44 55 42 94 18 06 67

i=4 12 42 44 55 94 18 06 67

i=5 12 42 44 55 94 18 06 67

i=6 12 18 42 44 55 94 06 67

i=7 06 12 18 42 44 55 94 67

i=8 06 12 18 42 44 55 67 94

Алгоритм этой сортировки представим в виде:

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

x = a[i];

включение x на соответствующее место среди a[1],...,a[i]

}

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

1. Найден элемент a_j с ключом, меньшим чем ключ у x.

2. Достигнут левый конец готовой последовательности.

На языке C++ функция сортировки с помощью вставок выглядит следующим образом.

void SortInsert(int n, int a[])

{ /* Сортировка с помощью вставки */

int i,j,x;

/* сдвигаем все элементы массива a на 1 позицию вправо */

for(i=n; i>0; i--) a[i]=a[i-1];

for(i=2; i<=n; i++) {

x=a[i];

a[0]=x; j=i-1;

while(x<a[j]) {

a[j+1]=a[j]; j=j-1;

}

a[j+1]=x;

}

/* сдвигаем все элементы массива a на 1 позицию влево */

for(i=0; i<n; i++) a[i]=a[i+1];

}

Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом "барьера". Здесь его легко применить, поставив барьер a₀ со значением x. Заметим, что для этого необходимо расширить величину массива a до n+1. В этом случае элемент a[0] служит "барьером", а сортируемые значения последовательно располагаются в элементах a[1], a[2], …, a[n].

Данный алгоритм описывает процесс устойчивой сортировки: порядок элементов с равными ключами при нем остается неизменным.

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

void BinarInsert(int n, int a[])

{ /* Сортировка вставками с методом деления пополам */

int i,j,m,L,r,x;

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

x=a[i]; L=0; r=i-1;

while(L<=r) {

m=(L+r)/2;

if(a[m]>x) r=m-1; else L=m+1;

}

for(j=i-1; j>=L; j--) a[j+1]=a[j];

a[L]=x;

}

}