Сортування включенням

Сортування включенням (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.