СОРТИРОВКА СЛИЯНИЕМ

[spawn969]

попался мне курсач с заданием разработать программу внешней сортировки с использованием однофазного естественного слияния на языке Pascal, нигде не нашел данной проги, везде описываются 3-х ленточные двухфазные сортировки, ведь естественное слияние состоит из 2 фаз:фазы распределения и фазы слияния. Но можно получить однофазную используя 4-х путевое слияние, т.е. 4 файла, при этом фазы объединяются в одну. Помогите с программой, срочно нужно, любой интересующий материал могу предоставить по этой теме в том числе исходные коды программ

[spawn969]

Вот еще некоторая информация

Однофазная сортировка простым слиянием

Фаза разделения файла А на два файла В и С не относится к сортировке. Она
непродуктивна, хотя и заниммает половину всех операций по переписи.
Очевидным улучшением (по быстродействию, но не по занимаемой памяти)
рассмотренного выше алгоритма является объединение фазы разделения с фазой
слияния.
Вместо слияния в один файл результаты слияния необходимо сразу распределять по
двум файлам, которые станут исходными для последующего прохода.
Такая сортировка называется однофазовой сортировкой простым слиянием. очевидно,
что для такой сортировки требуется уже не три, а четыре дополнительных файла.
Рассмотрим выполнение однофазной сортировки на примере.
Пусть задан файл А: 55 12 87 76 98 24 84 27
Разбиваем его на два файла:
С - 55 12 87 76 D - 55 98 84 87 С - 12 24 55 98

B - 98 24 84 27 E - 12 24 27 76 B - 27 76 84 87

A - 12 24 27 55 76 84 87 98


Сортировка естественным слиянием

В случае прямого слияния мы не получаем никакого преимущества, если данные уже
являются частично упорядоченными. Размер сливаемых при каждом проходе
последовательностей не зависит от существования более длинных уже упорядоченных
последовательностей, которые можно было бы просто объединить.
Сортировка, при которой всегда сливаются две самые длинные из возможных
последовательностей, назвается естественным слиянием.
Эта сортировка является двухфазной сортировкой слиянием с тремя
лентами(файлами).
Максимальную упорядоченную последовательность будем называть серией.
Пусть имеется начальный файл А. Каждый проход состоит из фазы распределения
серий из фалйа А поровну в файлы В и С и фазы слияния, объединяющей серии из
файлов В и С в файл А.
Процесс сортировки заканчивается, как только в файле А останется только одна
серия.
Рассмотрим сортировку естественным слиянием на примере (серии подчеркнуты).
Пусть задан файл А:

А - 17 31 05 59 13 41 43 76 11 23 29 47 03 07 71 02 19 57 37
61

B - 17 31 13 41 43 76 03 07 71 37 61

C - 05 59 11 23 29 47 02 19 57

A - 05 17 31 59 11 13 23 29 41 43 47 76 02 03 07 19 57 71 37 61

B - 05 17 31 59 02 03 07 19 57 71

C - 11 13 23 29 41 43 47 76 37 61

A - 05 11 13 17 23 29 31 41 43 47 59 76 02 03 07 19 37 57 61 71

B - 05 11 13 17 23 29 31 41 43 47 59 76

C - 02 03 07 19 37 57 61 71

A - 02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 71 76
Hа основе рассмотренного выше алгоритма легко получить алгоритм однофазной
сортировки естественным слиянием с четырьмя файлами.

[spawn969]

нткто не знает что ли

[p51x]

Вирт знаеет, почитайте его книгу

[spawn969]

ничего дельного нет в этой книге про однофазное естественное слияние

[spawn969]

вот как то так