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

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

На каждом шаге ищем минимальный элемент в ещё не отсортированной части массива и ставим его в её начало. Слева постепенно растёт отсортированная часть.

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

Ввести n и массив a.
Для i от 1 до n − 1: считать k = i номером минимума.
Для j от i + 1 до n: если a[j] < a[k], то k = j.
Поменять местами a[i] и a[k].
Вывести массив.

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

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

Вход	a = [64, 25, 12, 22]
Шаг 1	i = 1: минимум 12 (k = 3), обмен → [12, 25, 64, 22]
Шаг 2	i = 2: минимум 22 (k = 4), обмен → [12, 22, 64, 25]
Шаг 3	i = 3: минимум 25 (k = 4), обмен → [12, 22, 25, 64]
Результат	12 22 25 64

Решение на Python

n = int(input())
a = list(map(int, input().split()))
for i in range(n - 1):
    k = i
    for j in range(i + 1, n):
        if a[j] < a[k]:
            k = j
    a[i], a[k] = a[k], a[i]
print(*a)

Решение на Pascal

var a: array[1..100] of integer;
    n, i, j, k, t: integer;
begin
  readln(n);
  for i := 1 to n do read(a[i]);
  for i := 1 to n - 1 do
  begin
    k := i;
    for j := i + 1 to n do
      if a[j] < a[k] then k := j;
    t := a[i]; a[i] := a[k]; a[k] := t;
  end;
  for i := 1 to n do write(a[i], ' ');
end.

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

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

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

Сложность

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

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

Запоминать значение минимума вместо его номера — потом не с чем делать обмен.
Обнулять k внутри внутреннего цикла.
Начинать внутренний цикл с j = 1: тогда «портится» уже отсортированная часть.