end; if M[l] =
end;
if M[l] = sample then Search2:= true
else Search2:= false
end;
type
index1 = 0..N-1; {N>1}
massive1 = array [index1] of item;
procedure SelectionSort (var Mas: massive1);
var i: index1;
begin
for i := (N-1) downto 1 do
Swap(Mas[i], Mas[IndexMax(Mas,0,i)]);
end;
Трудоемкость этого алгоритма O(N2), поскольку фактически используется двойной цикл: внешний цикл с параметром и внутренний, в теле IndexMax,- той же разновидности. Так как оба цикла отрабатывают до конца, то количество шагов алгоритма никак не зависит от контекста и определено только длиной вектора.
Упражнение #1.
Каково точное число алгоритмических шагов процедуры SelectionSort при обработке вектора длины N?
Упражнение #2.
Как мы знаем, N различных значений можно разместить в векторе N! способами, иначе говоря, можно построить N! векторов. Применение к любому из них сортировки выбором потребует одного и того же числа "укрупненных" шагов, составляющих содержание процедуры
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
