Laboratornaya_rabota_7


Лабораторная работа №6 Сортировка слиянием

1. Цель и задачи работы

Изучить метод сортировки слиянием файлов и массивов в памяти. Написать программы, иллюстрирующие изученные принципы.

2. Теоретические сведения

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

Слияние означает объединение одного или более упорядоченных файлов в один упорядоченный файл. Можно, например, слить два подфайла – 503 703 765 и 087 512 677, получив 087 503 512 677 703 765. Простой способ сделать это – сравнить два наименьших элемента, вывести наименьший из них и повторить процедуру. Начав с

получим

затем

и т.д. Необходимо позаботиться о действиях на случай, когда исчерпается один из файлов. Эта простая процедура, по существу, наилучший из возможных способов слияния на традиционной ЭВМ, если m ( n.
Алгоритм М (Двухпутевое слияние}. Этот алгоритм осуществляет слияние упорядоченных массивов 13 EMBED Equation.DSMT4 1415и 13 EMBED Equation.DSMT4 1415в массив 13 EMBED Equation.DSMT4 1415 ( рис. 1).
Ml. [Начальная установка.] Установить 13 EMBED Equation.DSMT4 1415.
М2. [Найти наименьший элемент.] Если 13 EMBED Equation.DSMT4 1415, перейти к шагу МЗ; в противном случае перейти к шагу М5.
МЗ. [Вывести 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415. Если 13 EMBED Equation.DSMT4 1415, вернуться к шагу М2.
М4. [Передать 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415 и завершить выполнение алгоритма.
М5. [Вывести 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415. Если 13 EMBED Equation.DSMT4 1415, вернуться к шагу М2.
М6. [Передать 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415 и завершить выполнение алгоритма.


Рис. 1. Слияние 13 EMBED Equation.DSMT4 1415и 13 EMBED Equation.DSMT4 1415

Общий объем работы, выполняемой алгоритмом, по существу, пропорционален m+n, поэтому ясно, что слияние - более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подфайлы до тех пор, пока не будет отсортирован весь файл. Такой подход можно рассматривать как развитие идеи сортировки вставками: вставка нового элемента в упорядоченный файл – частный случай слияния, при n=1. Если нужно ускорить процесс вставок, то можно рассмотреть вставку нескольких элементов за раз, группируя их, а это естественным образом приводит к общей идеи сортировки слиянием. С исторической точки зрения метод слияний – один из самых первых методов, предназначенных для сортировки на ЭВМ; он был предложен Джоном фон Нейманом еще в 1945 году.
Таблица 1
СОРТИРОВКА МЕТОДОМ ЕСТЕСТВЕННОГО СЛИЯНИЯ


Таблица 1 иллюстрирует сортировку слиянием, когда «свечка сжигается с обоих концов». Мы анализируем исходный файл слева и справа, двигаясь к середине. Рассмотрим переход от второй строки к третьей. Слева видим возрастающий отрезок 503 703 765, а справа, если читать справа налево, имеем отрезок 087 512 677. Слияние этих двух последовательностей дает подфайл 087 503 512 677 703 765, который помещается слева в третьей строке. Затем ключи 061 612 908 в строке 2 сливаются с 170 509 897, и результат (061 170 509 612 897 908) записывается справа в строке 3. Наконец, 154 275 426 653 сливается с 653 ( перекрытие обнаруживается прежде, чем оно может привести к вредным последствиям), и результат записывается слева. Точно также строка 2 получилась из исходного файла в строке 1.
Вертикальными линиями в таблице 1 отмечены границы между отрезками. Это так называемые «ступеньки вниз», где меньший элемент следует за большим. Такой метод называют «естественным» слиянием, потому что он использует отрезки, которые естественно образуются в исходном файле. Если файл случаен, то в нем около 1/2N возрастающих отрезков. При каждом просмотре число отрезков сокращается вдвое. Таким образом, число просмотров составляет примерно около log2N.

Простое двух путевое слияние

В вышеозначенном алгоритме границы между отрезками полностью определены «ступеньками вниз». Такой подход обладает тем возможным преимуществом, что исходные файлы с преобладанием возрастающего или убывающего расположения элементов могут обрабатываться очень быстро, но при этом замедляется основной цикл вычислений. Вместо проверок ступенек вниз можно принудительно установить длину отрезков, считая, что все отрезки исходного файла имеют длину 1. После первого просмотра все отрезки, кроме, возможно, последнего, имеют длину 2 и т.д.
При сортировке записей 13 EMBED Equation.DSMT4 1415 используются две области памяти, в каждой из которых может содержаться N записей. Для удобства обозначим записи, находящиеся во второй области, через 13 EMBED Equation.DSMT4 1415, хотя в действительности запись 13 EMBED Equation.DSMT4 1415 может и не примыкать непосредственно к 13 EMBED Equation.DSMT4 1415. Начальное содержимое записей 13 EMBED Equation.DSMT4 1415 не имеет значения. После завершения сортировки ключи будут упорядочены таким образом: 13 EMBED Equation.DSMT4 1415 (рис. 2).
N1. [Начальная установка.] Установить 13 EMBED Equation.DSMT4 1415. (При s = 0 будем пересылать записи из области (13 EMBED Equation.DSMT4 1415) в область (13 EMBED Equation.DSMT4 1415), при s = 1 области по отношению к пересылкам поменяются ролями.)
N2. [Подготовка к просмотру.] Если s = 0, установить 13 EMBED Equation.DSMT4 1415; если s=l, установить 13 EMBED Equation.DSMT4 141513 EMBED Equation.DSMT4 1415 (Переменные 13 EMBED Equation.DSMT4 1415 указывают текущие позиции во "входных массивах'; из которых выполняется чтение, и в "выходных массивах'; в которые осуществляется запись. Установить 13 EMBED Equation.DSMT4 1415. (Переменная d задает текущее направление вывода, f устанавливается равной 0, если необходимы дальнейшие просмотры.)
N3. [Сравнение 13 EMBED Equation.DSMT4 1415] Если 13 EMBED Equation.DSMT4 1415, перейти к шагу N8. Если i=j, установить 13 EMBED Equation.DSMT4 1415 и перейти к шагу N13.
N4. [Пересылка 13 EMBED Equation.DSMT4 1415] (Шаги N4-N7 аналогичны шагам МЗ-М4 алгоритма М.) Установить 13 EMBED Equation.DSMT4 1415.
N5. [Ступенька вниз?] Увеличить i на 1. Далее, если 13 EMBED Equation.DSMT4 1415 вернуться к шагу N3.
N6. [Пересылка 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415.
N7. [Ступенька вниз?] Уменьшить j на 1. Далее, если 13 EMBED Equation.DSMT4 1415, вернуться к шагу N6; иначе перейти к шагу N12.
N8. [Пересылка 13 EMBED Equation.DSMT4 1415] (Шаги N8-N11 двойственны шагам N4-N7.) Установить 13 EMBED Equation.DSMT4 1415
N9. [Ступенька вниз?] Уменьшить j на 1. Далее, если 13 EMBED Equation.DSMT4 1415, вернуться к шагу N3.
N10. [Пересылка 13 EMBED Equation.DSMT4 1415] Установить 13 EMBED Equation.DSMT4 1415.
N11. [Ступенька вниз?] Увеличить i на 1. Далее, если 13 EMBED Equation.DSMT4 1415, вернуться к шагу N10.
N12. [Переключение направления.] Установить 13 EMBED Equation.DSMT4 1415и выполнить замену 13 EMBED Equation.DSMT4 1415. Вернуться к шагу N3.
N13. [Переключение областей.] Если f = 0, установить 13 EMBED Equation.DSMT4 1415 и вернуться к шагу N2. В противном случае сортировка будет завершена. Если s = 0, установить 13 EMBED Equation.DSMT4 1415. (Если результат можно оставить в области 13 EMBED Equation.DSMT4 1415, примерно в половине случаев последнее копирование оказывается необязательным.)

Рис. 2. Сортировка методом слияния.


Таблица 2.
503|
087|
512|
061|
908|
170|
897|
275|
|653
|426
|154
|509
|612
|677
|765
|703

503
703|
512
677|
509
908|
426
897|
|653
275
|170
154
|612
061
|765
087

087
503
703
765|
154
170
509
908|
|897
653
426
275
|677
612
512
061

061
087
503
512
612
677
703
765|
|908
897
653
509
426
275
170
154

061
087
154
170
275
426
503
509
512
612
653
677
703
765
897
908


Пример работы алгоритма в таблице 2. Данный метод справедлив и тогда, когда N не является степенью числа 2; сливаемые отрезки не все имеют длину 2k.
Рассмотрим оба алгоритма с точки зрения структур данных. Почему нам необходима память под 2n, а не под N записей? Причина проста: мы работаем с двумя списками. Но в любой момент времени половина памяти не используется, и очевидно, что в данном случае, следовало бы воспользоваться связным распределением памяти.

Порядок выполнения работы

Задать файлы, содержащие случайные числовые значения.
Произвести сортировку в соответствии с индивидуальным заданием.
Результат работы программы вывести в файл и на дисплей.

3. Варианты заданий

Написать программу сортировки слиянием по возрастанию двух файлов разного размера, используя метод естественного двух путевого слияния.
Написать программу сортировки слиянием по убыванию двух файлов разного размера, используя метод естественного двух путевого слияния.
Написать программу сортировки слиянием массива в памяти по возрастанию, используя метод естественного двух путевого слияния.
Написать программу сортировки слиянием массива в памяти по убыванию, используя метод естественного двух путевого слияния.
Написать программу сортировки слиянием двух файлов по возрастанию, обрабатывать заданное число записей в каждом из файлов. Использовать метод естественного двух путевого слияния.
Написать программу сортировки слиянием двух файлов по убыванию, обрабатывать заданное число записей в каждом из файлов. Использовать метод естественного двух путевого слияния.
Написать программу сортировки слиянием по возрастанию массива в памяти, обрабатывая указанное число записей от начала массива. Использовать метод естественного двух путевого слияния.
Написать программу сортировки слиянием по убыванию массива в памяти, обрабатывая указанное число записей от начала массива. Использовать метод естественного двух путевого слияния.
Написать программу сортировки слиянием по возрастанию массива в памяти, обрабатывая указанное число записей от концов массива. Использовать метод естественного двух путевого слияния.
Написать программу сортировки слиянием по убыванию массива в памяти, обрабатывая указанное число записей от концов массива. Использовать метод естественного двух путевого слияния.
Выполнить задание варианта 1), используя метод простого двух путевого слияния.
Выполнить задание варианта 2), используя метод простого двух путевого слияния.
Выполнить задание варианта 3), используя метод простого двух путевого слияния.
Выполнить задание варианта 4), используя метод простого двух путевого слияния.
Выполнить задание варианта 5), используя метод простого двух путевого слияния.
Выполнить задание варианта 6), используя метод простого двух путевого слияния.
Выполнить задание варианта 7), используя метод простого двух путевого слияния.
Выполнить задание варианта 8), используя метод простого двух путевого слияния.
Выполнить задание варианта 9), используя метод простого двух путевого слияния.
Выполнить задание варианта 10), используя метод простого двух путевого слияния.


4. Указания по составлению отчета

Отчет должен содержать:
- название, цель лабораторной работы,
- постановку и описание задачи,
- решение задачи (схемы алгоритмов программ, подпрограмм),
- текст составленной программы в среде Borland Pascal,
- тестовый пример,
- инструкцию пользователя,
- инструкцию программиста,
- краткие выводы.



Библиографический список

Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы. Т.2. М.: Мир, 1977.

Приложенные файлы

  • doc 17752453
    Размер файла: 556 kB Загрузок: 0

Добавить комментарий