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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

74
2. Используя алгоритм M обменной сортировки со слиянием, от-
сортируйте последовательность из шестнадцати записей: (503 «коли»),
(87 «скажут»), (512 «сам»), (61 «Что»), (908 «?»), (170 «тебе»), (897 «мо-
жешь»), (275 «другие»), (653 «себе»), (426 «,»), (154 «о»), (509 «ты»),
(612 «о»), (677 «ничего»), (765 «не»), (703 «сказать»).
3. Выполните с параметром M = 5 алгоритм Q обменной сортиров-
ки с разделением для последовательности из четырнадцати записей:
(39 «,»), (16 «у»), (80 «отдохнуть), (59 «;»), (16 «тебя»), (40 «заткни»),
(22 «есть»), (13 «Если»), (86 «фонтану»), (63 «дай»), (81 «и»), (93 «.»),
(23 «фонтан»), (44 «его»).
13. СОРТИРОВКА ПОСРЕДСТВОМ ВЫБОРА
Простейшая сортировка посредством выбора сводится к следующему:
а) выбрать в области ввода запись с наименьшим ключом; скопиро-
вать эту запись в область вывода и заменить ключ этой записи в области
ввода значением «∞», которое по предположению больше любого реаль-
ного ключа;
б) повторить шаг (а). На этот раз в область вывода будет скопиро-
вана запись с ключом, наименьшим из невыбранных ещё записей, так как
ранее наименьший ключ был заменён на «∞»;
в) повторять шаг (а) до тех пор, пока в область вывода не будут
скопированы все N записей.
Для наших традиционных шестнадцати ключей после первого вы-
полнения шага (а) содержимое областей ввода и вывода будет следую-
щим:
Область ввода
503
87
512
∞
908
170
897
275
653
426
154
509
612
677
765
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Область вывода
61
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
После второго выполнения шага (а):
Область ввода
503
∞
512
∞
908
170
897
275
653
426
154
509
612
677
765
703
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Область вывода
61
87
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Наконец, после шестнадцатого выполнения:

Страницы