Сортировка методом прямого выбора
Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом a 1.
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый "большой" элемент.
Алгоритм формулируется так:
| for i = 1 to n - 1
x = a(i) k = i for j = i + 1 to n if a(j) < x then k = j x = a(k) endif next j a(k) = a(i) a(i) = x next i return | for i := 1 to n - 1 do
begin x := a[i]; k := i; for j := i + 1 to n do if a[j] < x then begin k := j; x := a[k]; end; a[k] := a[i]; a[i] := x; end; |
Эффективность алгоритма:
Число сравнений ключей C, очевидно, не зависит от начального порядка ключей. Можно сказать, что в этом смысле поведение этого метода менее естественно, чем поведение прямого включения. Для C при любом расположении ключей имеем:
C = n(n-1)/2
Порядок числа сравнений, таким образом, О(n2)
Число перестановок минимально Мmin = 3(n - 1) в случае изначально упорядоченных ключей и максимально, Мmax = 3(n - 1) + С, т.е. порядок О(n2), если первоначально ключи располагались в обратном порядке.
В худшем случае сортировка прямым выбором дает порядок n2, как для числа сравнений, так и для числа перемещений.
