Int i,j,k,Key;

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

Key=t[k]; // Key – очередной вставляемый ключ

// от k-1 ключа двигаемся влево в поисках первого

// ключа, который меньше Key

// совмещаем поиск места вставки со сдвигом ключей вправо

for(j=k-1; j>=0; j--){

if(t[j]<Key){

break; // нашли

}

t[j+1]=t[j];

}

// новый ключ должен быть установлен в позицию t_j+1

t[j+1]=Key;

}

}

При поиске места вставки k-го ключа необходимо пройти в среднем k/2 ключей, выполняя сравнения и сдвиги. Таким образом, порядок времени работы алгоритма опять составляет величину порядка N². Время поиска места вставки можно уменьшить до ~logN, используя дихотомию, однако количество сдвигов от этого не уменьшится.

9.2.4.6. Сортировка методом "пузырька"

Проходим массив ключей слева направо, сравнивая соседние ключи. Если они стоят не по порядку, меняем их местами. Если в процессе просмотра не было обменов местами, то работа закончена, в противном случае повторяем процесс.

void BubbleSort(int n, int t[]){

bool b; // признак того, что в просмотре были обмены

do {

b=false;

for(int k=0; k<n-1; k++){

if(t[k]>t[k+1]){

swap(t[k],t[k+1]);

b=true;

}

}

} while(b);

}

Метод "пузырька" носит такое название, потому что в результате одного просмотра таблицы запись с наибольшим значением ключа перемещается вверх (если считать, что в верхней части таблицы располагаются наибольшие значения ключей), то есть всплывает как пузырек воздуха в жидкости. Время работы алгоритма пропорционально N². Анализ алгоритма довольно сложен и здесь не приводится.

Быстродействие можно несколько улучшить, если просма­тривать массив не далее места последнего обмена местами в предыдущем просмотре, поскольку все ключи правее места последнего обмена уже стоят на своих окончательных местах ("всплыли"). Еще одно усовершенствование – просматривать массив ключей поочередно слева направо, а затем справа налево. Такой метод называется шейкер – сортировкой. Предложенные усовершенствования улучшают быстродействие, однако время работы остается пропорциональным N².