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

Идея метода: находится максимальный элемент массива и меняется местами с последним элементом (с номером 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.
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.
Онлайн всего: 2
Гостей: 2
Пользователей: 0

STUDLAB Сообщить про опечатку на сайте