Сортировка методом прямого выбора
Begin
Begin
Begin
Begin
Var
i,j,k: longint;
x,y: single;
nMove:=0;
nCompare:=0;
fori:=2 tonCurr do
forj:= nCurr downto i do
x := A[j-1];
y := A[j];
Inc(nMove, 2);
Inc(nCompare);
// ifA[j - 1] > A[j] then
ifx > y then
A[j - 1] := y;
A[j] := x;
Inc(nMove, 2);
end;
end;
end;
end;
Количество сравнений (nCompare):
| i | Min | Max | Average |
| n-1 | n-1 | n-1 | |
| n-2 | n-2 | n-2 | |
| n-3 | n-3 | n-3 | |
| … | … | … | … |
 i
| n-i+1 | n-i+1 | n-i+1 |
| … | … | … | … |
| n | |||
| ∑ | 
n2/2-n/2
| 
n2/2-n/2
| 
n2/2-n/2
|
Количество переносов (nMove):
| i | Min | Max | Average |
| 2(n-1) | 4(n-1) | 3(n-1) | |
| 2(n-2) | 4(n-2) | 3(n-2) | |
| 2(n-3) | 4(n-3) | 3(n-3) | |
| … | … | … | … |
| i
| 2(n-i+1) | 4(n-i+1) | 3(n-i+1) |
| … | … | … | … |
| n | |||
| ∑ | 
n2-n
| 
2n2-2n
| 
3/2(n2-n)
|
На первом шаге разыскивается наименьший из n элементов массива, после чего он обменивается значениями с первым элементом.
На втором шаге разыскивается наименьший из оставшихся n-1 элементов массива, после чего он обменивается значениями с вторым элементом.
И т.д.
Текст процедуры:
procedureStraightSelectionSort;