История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2020-11-03 | 56 |
5.00
из
|
Заказать работу |
|
|
0. В готовую подпоследовательность записывается а1, во входную – а2,....аn.
1. i = 2.
2 Переносим элемент х = а из входной подпоследовательности в готовую так, чтобы готовая подпоследовательность осталась под сортированной. Для этого:
а) расширяем готовую подпоследовательность слева: а0 = х - барьер;
б) просматривая элементы готовой подпоследоватепьности слева направо,
находим такой номер j что и ai <= x < ai +1;
в) если j = j - 1, то переходим к пункту г), иначе расширяем готовую
подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо;
г) ai+1 = x
д) i = i + 1. Если i <=n, то переходим к п.2, иначе сортировка заканчивается..
Таблица 4.1
Начальные ключи | 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 | 94 | 94 | 67 |
i = 8 | 06 | 12 | 18 | 42 | 44 | 55 | 67 | 94 |
Алгоритм сортировки простыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность а2,....аn, в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарной поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.
Словесное описание алгоритма
0. В готовую подпоследовательность записывается а1, во входную а2,....аn.
1. i = 2
2 Переносим элемент х = а из входной подпоследовательности в готовую так, чтобы последняя осталась под сортированной. Для этого:
а) организуем бинарный поиск места включения х в готовую подпоследовательность: находим срединный элемент готовой подпоследовательности – am, где m =] i/2[, и сравниваем его с х. Если am > х то ведем далее поиск в левой половине готовой подпоследовательности, т. е. опять находим срединный элемент и сравниваем его с х и т. д., пока не найдем номер j такой, что ai <= x < ai+1, иначе аналогично ведем поиск в правой половине готовой подпоследовательности;
|
б) если j = j – 1, то переходим к пункту в), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы, начиная с ai вправо;
в) ai +1 = х
3. i=i+1. Если i <= n, то переходим к п.2, иначе сортировка заканчивается.
Сортировка простым выбором
Этот метод основан на следующем правиле:
1. Выбирается элемент с наименьшим ключом.
2. Он меняется местами с первым элементом аi.
Эти операции затем повторяются с оставшимися n-1 элементами, затем с n-2 элементами, пока не останется только один элемент - наибольший. Этот метод продемонстрирован на тех же восьми ключах в табл. 4.2.
Этот метод называемый сортировкой простым выбором, в некотором смысле противоположен сортировке простыми включениями; при сортировке простыми включениями на каждом шаге рассматривается только один очередной элемент входной последовательности и все элементы готового массива для нахождения места включения; при сортировке простым выбором рассматриваются все элементы входного массива для нахождения элемента с наименьшим ключом, и этот один очередной элемент отправляется в готовую последовательность.
Таблица 4.2
Начальные ключи 44 55 12 42 94 18 06 67
06 55 12 42 94 18 44 67
06 12 55 42 94 18 44 67
06 12 18 42 94 55 44 67
. 06 12 18 42 94 55 44 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!