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

Сортировка вставками (insertion sort) - это алгоритм сортировка, в котором все элементы массива просматриваются поочередно, при этом каждый элемент размещается в соответственное место среди ранее упорядоченных значений.

Алгоритм работы сортировки вставками заключается в следующем:

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

Код программы алгоритма “Сортировки вставками”

{$CODEPAGE UTF8}
program InsertionSort;
const
  arrayLength = 10;
var
  inputArray : array [1..arrayLength] of integer;
  i, j, key, tempValue: integer;

begin
  randomize;
  writeln ('Исходный массив: ');
  {заполнение массива случайными числами}
  for i := 1 to arrayLength do
  begin
    inputArray[i] := random(100);
    write (inputArray[i]:4);
  end;
  writeln;

  {сортировка вставками}

  for i := 2 to arrayLength do
    begin
      key := inputArray[i];
      j := i;
      while (j > 1) and (inputArray[j - 1] > key) do
        begin
          {обмен элементов}
          tempValue :=  inputArray[j];
          inputArray[j] := inputArray[j - 1];
          inputArray[j - 1] := tempValue;
          j := j - 1;
        end;
      inputArray[j] := key;
    end;

  writeln ('Отсортированный массив: ');
  for i := 1 to arrayLength do
    write (inputArray[i]:4);
  readln;
end.