Pascal. Задача 8-21

Отсортировать массив целых чисел, введенных пользователем, методом простых вставок.

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

Сортировка методом простых вставок

3-ий элемент перемещаем на место четвертого, второй элемент перемещаем на место третьего. На место второго элемента вставляем значение из буфера.

Таким образом просматриваются все элементы массива по очереди.

Сортировка методом простых вставок считается эффективной для почти упорядоченных массивов.

Решение

const
  N = 10;
var
  i, j, tmp : integer;
  a : array[1..N] of integer;
  flag : boolean;
begin
  for i := 1 to N do begin
    Write('Введите элемент массива ', i, ': ');
    Readln(a[i]);
  end;
  for i := 2 to N do begin
    j := i;
    tmp := a[i];
    while (j > 1) and (tmp < a[j - 1]) do begin
      a[j] := a[j - 1];
      Dec(j);
    end;
    if j < i then a[j] := tmp;
  end;
  for i := 1 to N do Write(a[i], ' ');
  Writeln();
end.