Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2019-11-19 | 195 |
5.00
из
|
Заказать работу |
|
|
(15 неделя, 1 час)
Прямое включение. Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже “готовую” последовательность а1,…, аi-1 и исходную последовательность. При каждом шаге, начиная с i = 2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i – ный элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.
Пример сортировки с помощью прямого включения:
Начальные ключи | 44 | 55 | 12 | 42 | 94 | 18 | 06 | 67 |
i = 2 | 44 | 55 | 12 | 42 | 94 | 18 | 06 | 67 |
i = 3 | 12 | 44 | 55 | 42 | 94 | 18 | 06 | 67 |
i = 4 | 12 | 42 | 44 | 55 | 94 | 18 | 06 | 67 |
i = 5 | 12 | 42 | 44 | 55 | 94 | 18 | 06 | 67 |
i = 6 | 12 | 18 | 42 | 44 | 55 | 94 | 06 | 67 |
i = 7 | 06 | 12 | 18 | 42 | 44 | 55 | 94 | 67 |
i = 8 | 06 | 12 | 18 | 42 | 44 | 55 | 67 | 94 |
Это процесс сортировки с помощью включения 8-ми случайно выбранных чисел. Алгоритм этой сортировки:
FOR i:=2 to n DO
x: = a[i];
{включение х на соответствующее место среди a[1]… a[i] }
END
В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать, т.е. х сравнивается с очередным элементов аj, а затем либо х вставляется на свободное место, либо аj сдвигается (передается) вправо и процесс «уходит» влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из 2-х условий:
1. Найден элемент аj с ключом, меньшим чем ключ у х.
2. Достигнут левый конец готовой последовательности.
Procedure StraightInsertion;
Var i, j: index; x: item;
Begin
For i:=2 то n DO
x: = a[i]; a[0]: = x; j: = 1;
WHILE x < a[j – 1] DO a[j]: = a[j – 1]; j: = j – 1; END;
a[j]: = x END
END STRAIGHT INSERTION
Индивидуальные задания
Выпишите результаты всех проходов алгоритма сортировки списка с помощью прямого включения
1. (7, 3, 9, 4, 2, 5, 6, 1, 8)
2. (8, 6, 4, 3, 9, 7, 5, 1, 2)
|
3. (1, 9, 6, 8, 4, 2, 7, 5, 3)
4. (6, 3, 2, 8, 4, 7, 5, 9, 1)
5. (4, 6, 8, 9, 5, 7, 3, 2, 1)
6. (4, 7, 5, 1, 2, 9, 8, 3, 6)
7. (8, 6, 2, 5, 9, 3, 4, 1, 7)
8. (3, 9, 6, 8, 4, 7, 1, 5, 2)
9. (23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4)
10. (2, 35, 8, 41, 9, 41, 11, 6, 58, 77, 23, 7)
11. (7, 13, 52, 77, 53, 56, 68, 2, 71, 22, 95, 58
12. (51, 50, 52, 94, 15, 25, 38, 68, 15, 44, 84, 25)
13. (81, 79, 64, 23, 38, 64, 92, 26, 24, 37, 8, 41)
14. (49, 10, 66, 3, 64, 36, 54, 49, 19, 1, 82, 77)
15. (88, 49, 17, 22, 19, 45, 96, 64, 28, 53, 29, 35)
16. (1, 36, 49, 27, 77, 60, 11, 42, 50, 66, 57, 44)
17. (6, 97, 35, 91, 92, 21, 84, 57, 59, 17, 10, 67)
18. (9, 5, 43, 76, 34, 20, 52, 39, 87, 51, 47, 1)
19. (43, 82, 28, 32, 9, 24, 35, 75, 85, 63, 52, 34)
20. (16, 52, 83, 84, 62, 91, 20, 37, 81, 22, 30, 26)
Прямой выбор. Этот прием основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом а1
3. Затем этот процесс повторяется с оставшимися n –1 элементами, n –2 элементами, и т.д. до тех пор, пока не останется один, самый большой элемент.
Процесс работы этим методом с теми же 8-мью ключами, что и таблица 2.1. приведен в таблице 2.2. алгоритм формируется так:
FOR i: = 1 to n – 1 do
присвоить k индекс наименьшего из а[i] … a[n];
поменять местами а[i] и a[k];
end
Применение сортировки с помощью прямого выбора
Начальные ключи | 44 | 55 | 12 | 42 | 94 | 18 | 06 | 67 |
i = 2 | 06 | 55 | 12 | 42 | 94 | 18 | 44 | 67 |
i = 3 | 06 | 12 | 55 | 42 | 94 | 18 | 44 | 67 |
i = 4 | 06 | 12 | 18 | 42 | 94 | 55 | 44 | 67 |
i = 5 | 06 | 12 | 18 | 42 | 94 | 55 | 44 | 67 |
i = 6 | 06 | 12 | 18 | 42 | 44 | 55 | 94 | 67 |
i = 7 | 06 | 12 | 18 | 42 | 44 | 55 | 94 | 67 |
i = 8 | 06 | 12 | 18 | 42 | 44 | 55 | 67 | 94 |
Такой метод – его называют прямым выбором в некотором смысле противоположен прямому включению. При прямом включении на каждом шаге рассматривается только один очередной элемент исходной последовательности и все элементы готовой последовательности, среди которых отыскивается точка включения; при прямом выборе для поиска одного элемента с наименьшим ключом просматриваются все элементы исходной последовательности и найденный помещается как очередной элемент в готовую последовательность. Полностью алгоритм прямого выбора приводится в программе 2.3.
PROCEDURE StraightSelection:
VAR i,j,k: intex; x: item;
BEGIN
FOR i: = 1 TO n - 1 DO
k: = i; x: = a[i];
FOR j: = i + 1 TO n DO
IF a[j] < x THEN k: = j; x: = a[k] END
END;
END StraightSelection
|
Прогр. Сортировка с помощью прямого выбора.
Индивидуальные задания
Выпишите результаты всех проходов алгоритма сортировки списка с помощью прямого выбора
1. (7, 3, 9, 4, 2, 5, 6, 1, 8)
2. (8, 6, 4, 3, 9, 7, 5, 1, 2)
3. (1, 9, 6, 8, 4, 2, 7, 5, 3)
4. (6, 3, 2, 8, 4, 7, 5, 9, 1)
5. (4, 6, 8, 9, 5, 7, 3, 2, 1)
6. (4, 7, 5, 1, 2, 9, 8, 3, 6)
7. (8, 6, 2, 5, 9, 3, 4, 1, 7)
8. (3, 9, 6, 8, 4, 7, 1, 5, 2)
9. (23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4)
10. (2, 35, 8, 41, 9, 41, 11, 6, 58, 77, 23, 7)
11. (7, 13, 52, 77, 53, 56, 68, 2, 71, 22, 95, 58
12. (51, 50, 52, 94, 15, 25, 38, 68, 15, 44, 84, 25)
13. (81, 79, 64, 23, 38, 64, 92, 26, 24, 37, 8, 41)
14. (49, 10, 66, 3, 64, 36, 54, 49, 19, 1, 82, 77)
15. (88, 49, 17, 22, 19, 45, 96, 64, 28, 53, 29, 35)
16. (1, 36, 49, 27, 77, 60, 11, 42, 50, 66, 57, 44)
17. (6, 97, 35, 91, 92, 21, 84, 57, 59, 17, 10, 67)
18. (9, 5, 43, 76, 34, 20, 52, 39, 87, 51, 47, 1)
19. (43, 82, 28, 32, 9, 24, 35, 75, 85, 63, 52, 34)
20. (16, 52, 83, 84, 62, 91, 20, 37, 81, 22, 30, 26)
|
|
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!