Стр. 86 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
84
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Алгоритм.
for (i=
1
; i<=n-
1
; i++) // до границы сортированных и
//несортированных элементов
{
j=i;
for (k=i+
1
; k<=n; k++)
{
if (x
j
<x
k
) j=k;
}
<x
j
и x
i
меняем местами>
}
Анализ быстродействия
. На первом шаге число сравнений (
n
-1). На
втором шаге (
n
-2).Всего сравнений
C
= (
n
-1) + (
n
-2) + … + 1 =
n
(
n
-1)/2 =
O
(
n
2
)
независимо от исходного порядка ключей.
Несмотря на неэффективность алгоритма сортировки выбором, идея
выбора может привести и к эффективному алгоритму сортировки. Весь вопрос
в том, чтобы найти более эффективный метод определения
i
-го наибольшего
имени. Этого можно добиться, используя механизм турнира с выбыванием.
Суть его такова: сравниваются (
x
1
:
х
2
); (
х
3
:
х
4
); (
х
5
:
х
6
); ...; (
x
n
-1
:
х
n
), затем
сравниваются “победители” (т. е. большие имена) этих сравнений и т. д.; эта
процедура для
n
= 16 выглядит следующим образом:
X
1
= 91
X
2
= 15
X
3
= 48
X
4
= 58
X
5
= 63
X
6
= 94
X
7
= 34
X
8
= 8
X
9
= 85
X
10
= 93
X
11
= 10
X
12
= 3
X
13
= 13
X
14
= 75
X
15
= 51
X
16
= 44
91
58
94
34
93
10
75
51
91
94
93
75
94
94
93
X
’
X
’’
X
’’’
Рис. 67. Выбор наибольшего элемента
