Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Топ:
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Оснащения врачебно-сестринской бригады.
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2017-09-28 | 691 |
5.00
из
|
Заказать работу |
|
|
1. Если Правая_граница = 0, то
Результат = 0
Иначе
1.1. Если Правая_граница = 1, то
Результат = А0
Иначе
1.1.1.Если Правая_граница = 2, то
Если А1 < А0
Результат = А1, А0
Иначе
Результат = А0, А1
1.1.2.Иначе
a) Упорядочить первую половину массива А:
Вызвать Сортировку(А; Левая_граница; Правая_граница/2);
b) Упорядочить вторую половину массива А:
Вызвать Сортировку (А; Левая_гр +Правая_гр/2+1; Правая_гр);
c) Слияние Первой и Второй половин массива А:
Слияние A [0… Левая_гр + Правая_гр/2] и
A [Левая_гр + Правая_гр/2 + 1; Правая_гр]
2. Вывести массив А.
3. Закончить.
Алгоритм 6. Сортировка Боуза- Нельсона
Этот метод реализует один из способов слияния. Он удобен для сортировки больших массивов, находящихся на устройствах последовательного доступа (например, винчестерах). Массив А разбивается на две половины: B и С. Эти половины сливаются в упорядоченные пары, объединяя первые элементы из B и С в первую пару, вторые – во вторую и т.д. Полученному массиву присваивается имя А, после чего операция повторяется. При этом пары сливаются в упорядоченные четверки. Предыдущие шаги повторяются: четверки сливаются в восьмерки и т.д., пока не будет упорядочен весь массив, т.к. длины частей каждый раз удваиваются. Если размер массива нечетный, или на некотором шаге получатся неполные части, то выполняют отдельно слияние начал, концов и центральной частей. Описанный алгоритм можно проиллюстрировать следующим примером.
Пример. Исходная последовательность
А = 44 55 12 42 94 18 06 67
Шаг 1
Первая половина B = 44 55 12 42
Вторая половина С = 94 18 06 67
А = 44 94 18 55 06 12 42 67 – для наглядности нечетные пары выделены.
Шаг 2
Первая половина B = 44 94 18 55
Вторая половина С = 06 12 42 67
А = 06 12 44 94 18 42 55 67 – выделены упорядоченные четверки.
|
Шаг 3
Первая половина B = 06 12 44 94
Вторая половина С = 18 42 55 67
А = 06 12 18 42 44 55 67 94 – отсортированный массив.
Судя по описанию, алгоритм проще всего реализовать с помощью рекурсии, причем, в отличие от традиционной сортировки слиянием он не требует дополнительной памяти. Обозначим r - расстояние между началами сливаемых частей, m - их размер и j - наименьший номер элемента. Будем считать, что выполняется сортировка по возрастанию.
Рекурсивный алгоритм сортировки Боуза- Нельсона
1. Слияние
1.1. Начало рекурсии. Если j+r ≤ n, то
1.1.1. Если m = 1, то
a) Если A[j] > A[j+r ], то
Поменять местами A[i ] и A[j +r].
1.2. Иначе
1.2.1. m = m / 2.
1.2.2. Выполнить Слияние «начал» от j до m с расстоянием r.
1.2.3. Если j+r+m ≤ n, то
Выполнить Слияние «концов» от j+m до m с расстоянием r.
1.2.4. Выполнить Слияние «центральной части» от j+m до m с расстоянием m - r.
2. Основная часть рекурсии
2.1. m = 1.
2.2. Повторять
2.3. Цикл слияния списков равного размера
2.3.1. j = 1.
2.3.2. Пока j+m ≤n
1) Выполнить Слияние (j,m,m);
2) j = j + 2 m
2.3.3. Удвоение размера списка перед началом нового прохода
m = 2 m.
Конец цикла 2.2, реализующего все слияния
Пока m < n.
3. Вывести массив А.
4. Закончить.
Число сравнений и пересылок при реализации сортировки методом Боуза - Нельсона в самом худшем случае пропорционально n log n, т.е. сложность алгоритма O(n log n). Дополнительная память не требуется.
Алгоритм 7. Быстрая сортировка
Метод использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Он реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.
В алгоритме используются два разнонаправленных процесса. Первый выполняется от начала массива и ищет элемент, больший опорного. Второй - работает с конца и ищет элемент, меньший опорного. Как только такие элементы найдены, производится их обмен местами. Далее поиск продолжается с того места, где процессы остановились.
|
Таким образом, когда процессы встречаются, любой элемент в первой части меньше любого во второй. Это значит, что их уже сравнивать друг с другом не придется. Остается только провести такую же операцию по отношению к полученным половинам, и так далее, пока в очередной части массива не останется один элемент. Это будет означать, что массив отсортирован. Очевидно, что наиболее удобный способ реализации рассмотренного метода – рекурсивный.
Общий алгоритм можно представить так.
1. Из массива выбирается некоторый опорный элемент, Опорный = a[i ], i=n /2.
2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, равные Опорному, - вправо.
3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.
4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.
В конце получится полностью отсортированная последовательность.
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!