Задачи / Сортировки / Сортировка вставками

Сортировка вставками: блок-схема и алгоритм

Так сортируют карты в руке: берём очередной элемент и сдвигаем вправо все бо́льшие элементы слева от него, пока не найдётся его место. Слева всегда отсортированная часть.

Алгоритм по шагам

Ввести n и массив a.
Для i от 2 до n: запомнить x = a[i], j = i − 1.
Пока j ≥ 1 и a[j] > x: сдвинуть a[j] на позицию j + 1 и уменьшить j.
Поставить x на позицию j + 1.
Вывести массив.

Открыть блок-схему в редакторе

Пример работы

Вход	a = [7, 3, 5, 1]
Шаг 1	i = 2: x = 3, сдвиг 7 → [3, 7, 5, 1]
Шаг 2	i = 3: x = 5, сдвиг 7 → [3, 5, 7, 1]
Шаг 3	i = 4: x = 1, сдвиг 7, 5, 3 → [1, 3, 5, 7]
Результат	1 3 5 7

Решение на Python

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x
print(*a)

Решение на Pascal

var a: array[1..100] of integer;
    n, i, j, x: integer;
begin
  readln(n);
  for i := 1 to n do read(a[i]);
  for i := 2 to n do
  begin
    x := a[i];
    j := i - 1;
    while (j >= 1) and (a[j] > x) do
    begin
      a[j + 1] := a[j];
      j := j - 1;
    end;
    a[j + 1] := x;
  end;
  for i := 1 to n do write(a[i], ' ');
end.

Код блок-схемы

Схема выше нарисована по этому псевдокоду. Скопируйте его в редактор блок-схем или нажмите «Открыть блок-схему в редакторе».

блок-схема: Сортировка вставками
начало
ввод n, массив a[1..n]
для i от 2 до n
    x = a[i]
    j = i − 1
    пока j ≥ 1 и a[j] > x
        a[j + 1] = a[j]
        j = j − 1
    a[j + 1] = x
вывод массив a
конец

Сложность

O(n²) в худшем случае, O(n) на почти отсортированном массиве. Память O(1). Сортировка устойчивая.

Частые ошибки

В Pascal условие (j >= 1) and (a[j] > x) без скобок не компилируется, а без проверки j ≥ 1 возможен выход за границу массива.
Записывать x в a[j] вместо a[j + 1].
Начинать внешний цикл с i = 1: первый элемент и так «отсортирован».