Допустим, что ключи t0…tk-1 уже упорядочены. В упорядоченной части последовательности найдем место для tk, на котором ключ tk не нарушает порядка, и вставим его туда, предварительно сдвинув вправо на одну позицию ключи от места вставки до tk. Также поступим с последующими ключами.
void InsertSort(int n, int t[]){
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];
}
// новый ключ должен быть установлен в позицию tj+1
t[j+1]=Key;
}
}
При поиске места вставки k-го ключа необходимо пройти в среднем k/2 ключей, выполняя сравнения и сдвиги. Таким образом, порядок времени работы алгоритма опять составляет величину порядка N2. Время поиска места вставки можно уменьшить до ~logN, используя дихотомию, однако количество сдвигов от этого не уменьшится.
9.2.4.6. Сортировка методом "пузырька"
Проходим массив ключей слева направо, сравнивая соседние ключи. Если они стоят не по порядку, меняем их местами. Если в процессе просмотра не было обменов местами, то работа закончена, в противном случае повторяем процесс.
void BubbleSort(int n, int t[]){
