Сортировка выбором
Идея метода: находится максимальный элемент массива и меняется местами с последним элементом (с номером N). Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум.
Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае коли-чество шагов внешнего цикла N div 2.
Вычислительная сложность сортировки выбором - величина порядка N*N, что обыч-но записывают как O(N*N). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.
Пример. Сортировка выбором по возрастанию массива A.
Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае коли-чество шагов внешнего цикла N div 2.
Вычислительная сложность сортировки выбором - величина порядка N*N, что обыч-но записывают как O(N*N). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.
Пример. Сортировка выбором по возрастанию массива A.
program Sort_Vybor1;
var A:array[1..100] of integer;
N,i,m,k,x : integer;
begin
write('количество элементов массива);
read(N);
for i:=1 to n do read(A[i]);
for k:=n downto 2 do {k- количество элементов для поиска max }
begin
m:=1; { m - место max }
for i:=2 to k do if A[i]>A[m] then m:=i;
{меняем местами элементы с номером m и номером k}
x:=A[m]; A[m]:=A[k]; A[k]:=x;
end;
for i:=1 to n do write(A[i],' '); {упорядоченный массив}
end.
