Сортування простим вибором

Сутність методу полягає у наступному. На першому кроці обирається найменший елемент і міняється місцями з першим. На другому кроці серед решти елементів знову обирається найменший елемент і міняється місцями з другим. Цей процес продовжується до повного впорядкування вихідного масиву. Проілюструємо роботу методу на прикладі масиву з 10 елементів. На кожному кроці найменший елемент виділятимемо іншим кольором.

Вихідний масив:

44  55  12  42  94  18  06  67  32  13

Після першого кроку:

06  55  12  42  94  18  44  67  32  13

Після другого кроку:

06  12  55  42  94  18  44  67  32  13

На останньому кроці

06  12  13  18  32  42  44  55  67  94

При записі алгоритму на кожному кроці доцільно при пошукові найменшого елементу запам’ятовувати не сам елемент, а його номер. Це спростить алгоритм. Процедура сортування простим вибором має такий вигляд:

procedure straightselection (var a: massiv);

var

i,j,k: integer;

x: integer;

n1,n: integer;

begin

{границі масиву}

n1:= Low(a);

n:= High (a);

{впорядкування}

for i:= n1 to n do

begin

  k:=i;

  for j:= i+1 to n do

  if a[j]<a[k] then k:=j;

  if  k >i then

  begin

  x:=a[i];

  a[i]:=a[k];

  a[k]:=x;

  end;

end;

end;

Число C порівнянь ключів не залежить від початкового порядку ключів:

C=1/2 (n² +n–1).

Мінімальне число пересилань у випадку початково  упорядкованих елементів має значення:

M_min=0

Найбільше значення ця величина приймає  у випадку, коли елементи вихідного масиву розташовані в зворотному порядку до впорядкування (тобто, впорядковані за спаданням):

M_max=trunc (n²/4).