Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Дисциплины:
2019-11-19 | 189 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!