Сортировка. Программирование (Паскаль), 9 класс

1. Сортировка

Программирование (Паскаль), 9 класс
1
Сортировка
Сортировка — это расстановка элементов списка
(массива) в заданном порядке.
Задача. Отсортировать элементы в порядке
возрастания (неубывания – если есть одинаковые).
Алгоритмы сортировки:
• простые, но медленные (при больших N)
• быстрые, но сложные…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Сортировка выбором

Программирование (Паскаль), 9 класс
2
Сортировка выбором
? Где должен стоять минимальный элемент?
• нашли минимальный, поставили его на первое место
Как?
с:= A[nMin];
A[nMin]:= A[1];
A[1]:= c;
?
? Что дальше?
• из оставшихся нашли минимальный, поставили его на
второе место и т.д.
5
–2
8
3
–1
–2
5
8
3
–1
–2
–1
8
3
5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Сортировка выбором

Программирование (Паскаль), 9 класс
3
Сортировка выбором
for i:=1 to N-1 do begin
{ ищем минимальный среди A[i]..A[N] }
не трогаем те, которые
уже поставлены
nMin:= i;
for j:=i+1 to N do
if A[j] < A[nMin] then
nMin:= j;
{ переставляем A[i] и A[nMin] }
c:=A[i];
Почему цикл до N-1?
A[i]:=A[nMin];
A[nMin]:=c;
end;
?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru