Методы программирования. Громов Ю.Ю - 75 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

75
Область ввода
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Область вывода
61
87
154
170
275
426
503
509
512
612
653
677
703
765
897
908
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Описанный метод требует (N – 1) сравнений каждый раз, когда вы-
бирается очередная запись, и требует отдельной области вывода в памя-
ти. Ликвидировать отмеченные недостатки можно следующим образом.
Не использовать ключ «∞» и выбранную запись перемещать в соответст-
вующую позицию, а запись, которая занимала эту позицию, переносить
на место выбранной. Тогда упомянутую выбранную запись не нужно рас-
сматривать вновь при последующих выборах.
Алгоритм S. (Сортировка посредством простого выбора.) Записи
R
1
, …, R
N
переразмещаются на том же месте. После завершения сортиров-
ки их ключи будут упорядочены: K
1
≤ … ≤ K
N
. Сортировка основана на
описанном выше методе, но для удобства сначала выбирается наибольший
элемент, затем – наибольший из оставшихся элементов и т.д.
S1. [Цикл по j.] Выполнить шаги S2 и S3 при j = N, N – 1, …, 2.
S2. [Поиск max {K
1
, …, K
j
}.] Найти наибольший из ключей K
j
,
K
j–1
, …, K
1
. Пусть это будет ключ K
i
, где i выбирается как можно большим.
S3. [Обмен.] Поменять местами записи R
i
и R
j
. (Теперь записи R
j
, …,
R
N
занимают свои окончательные позиции.) ■
Действие этого алгоритма на последовательность из шестнадцати
ключей будет следующим:
503
87
512
61
908
170
897
275
653
426
154
509
612
677
765
703
503
87
512
61
703
170
897
275
653
426
154
509
612
677
765
908
503
87
512
61
703
170
765
275
653
426
154
509
612
677
897
908
503
87
512
61
703
170
677
275
653
426
154
509
612
765
897
908
503
87
512
61
612
170
677
275
653
426
154
509
703
765
897
908
. . . .
61
87
154
170
275
426
503
509
512
612
653
677
703
765
897
908
Здесь полужирным шрифтом отмечены ключи обменивающихся местами
записей.
Отметим, что среднее время работы алгоритма S равно (2.5N
2
+
+ 3(N + 1)
H
N
+ 3.5N – 11)
u, т.е. он лишь немного медленнее простых
вставок.
С целью усовершенствования алгоритма простого выбора проанали-
зируем поиск максимума на шаге S2. Для определения максимума из
N элементов, основанном на сравнении пар элементов, действительно

Страницы