Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Сортировка естественным двухпутевым слиянием.
Рис. 5 иллюстрирует сортировку слиянием, когда мы продвигаемся с обоих концов, подобно методам быстрой сортировки, обменной сортировки и т.д. Мы анализируем исходный файл слева и справа, двигаясь к середине. Пропустим первую строку и рассмотрим вторую. Слева мы видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который перемещается слева в строке 3. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 987 и результат записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 (перекрытие обнаруживается раньше, чем оно может привести к нежелательным последствиям) и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1. Вертикальными линиями на рисунке отмечены границы между отрезками. Это так называемые ступеньки вниз, где меньший элемент следует за большим. В середине файла возникает двусмысленная ситуация, когда мы с обоих концов читаем один и тот же ключ. Описанный метод называют "естественным" слиянием, потому что он использует отрезки, которые "естественно" образуются в файле. Алгоритм Е (Сортировка естественным двухпутевым слиянием). При сортировке записей R1, …, RN используются две области памяти, каждая из которых может содержать N записей. Для удобства обозначим записи, находящиеся во второй области, через RN+1, …, R2N, хотя в действительности области не обязательно идти друг за другом. Начальное содержание второй области не имеет значение. После завершения алгоритма ключи будут упорядочены К1 £ …£ КN.
(Начальная установка) Установить s:=0 (при s=0 мы будем пересылать записи из области (R1,…RN) в область (RN+1, …, R2N); при s=1 наоборот.) (Подготовиться к просмотру) Если s=0, то установить i:=1, j:=N, k:=N+1, g:=2N, если s=1, то установить i:=N+1, j:=2N, k:=1, g:=N. (переменные i, j, k, g указывают текущие позиции во входных "файлах", откуда идет чтение, и в "выходных" файлах, куда идет запись; i и k – левые позиции, j и r – правые позиции.) Установить d:=1, f:=1 (Переменные d определяет текущее направление вывода, f устанавливается равной 0, если необходимы дальнейшие просмотры.)
(Сравнения Кi с Кj) Если Кi > Кj, то перейти к шагу Е8, если i=j (т.е. рассматриваем один и тот же элемент с разных концов), то установить Rk:=Ri и перейти к шагу Е13. (Пересылка Ri) (Шаги Е4-Е7 аналогичны шагам М3-М4 алгоритма М). Установить Rk:=Ri, k:=k+d. (Ступенька вниз?) Увеличить i на 1, Затем, если Кi–1 £ Кi, то возвратиться к шагу Е3. (Пересылка Rj) Установить Rk:=Rj, k:=k+d. (Ступенька вниз?). Уменьшить j на 1. Затем, если Кj+1 £ Кj, то возвратиться к шагу Е6, в противном случае перейти к шагу Е12. (Пересылка Rj) (Шаги Е8–Е11 двойственные по отношению к шагам Е4–Е7) Установить Rk:=Rj, k:=k+d. (Ступенька вниз?). Уменьшить j на 1. Затем, если Кj+1 £ Кj, то возвратиться к шагу Е3 (Пересылка Rj) Установить Rk:=Ri, k:=k+d. (Ступенька вниз?). Увеличить i на 1, Затем, если Кi–1 £ Кi, то возвратиться к шагу Е10. (Переключение направления). Установить f:=0, d:= – d и взаимозаменить k <-> g. Возвратиться к шагу Е3. (Переключение областей) Если f=0, то установить s:=1–s и возвратиться к шагу Е2, в противном случае сортировка завершена, если s=0, то установить (R1,…RN):= (RN+1, …, R2N) (если это критично). Если исходный файл случаен, то в нем около 1/2N возрастающих отрезков, так как Кi > Кi+1 с вероятностью 1/2. При каждом просмотре число отрезков сокращается вдвое. Число просмотров, как правило, составляет около lоg2 N. При каждом просмотре мы должны переписать все N записей, и большая часть времени затрачивается в шагах Е3, Е4, Е5, Е8, Е9. Общее время работы асимптотически приближается к 12.5Nlоg2N, как в среднем, так и худшем варианте. Это медленнее быстрой сортировки и не настолько лучше пирамидальной сортировки (16lоg2N), чтобы оправдать вдвое больший расход памяти.
|
||||||
Последнее изменение этой страницы: 2017-01-18; просмотров: 478; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.147.104.248 (0.004 с.) |