- •1. Инструментальные средства разработки программного обеспечения сапр
- •2. Абстрактные типы данных. Примеры и варианты реализации.
- •3. Прямые методы сортировки массивов
- •4. Быстрая сортировка
- •5. Сортировка Шелла
- •6. Пирамидальная сортировка.
- •7. Алгоритмы внешней сортировки (вс)
- •8. Бинарный поиск и поиск по бинарному дереву
- •9. Алгоритмы обхода бинарных деревьев и их применение в трансляции программ и обработке данных
- •10. Машинное представление деревьев.
- •11. Машинное представление графов
- •12. Процедура поиска в глубину и ее применение в задачах обработки данных
- •13. Формальные грамматики и языки. Классификация грамматик.
- •14. Синтаксические диаграммы
- •15. Фазы трансляции программ и варианты организации языковых процессоров
- •16. Лексический анализ программ. Организация работы сканера
- •17. Нисходящий грамматический разбор с возвратом.
- •18 Восходящий грамматический разбор программ.
- •19 Формы внутреннего представления программ в языковых процессорах сапр.
- •2. Польская запись.
- •20 Семантический анализ. Примеры организации семантических программ.
- •21. Машинно-независимая оптимизация программ
- •22 . Генерация кода в языковых процессорах сапр (Генерация кода в компиляторах)
- •23 Машинно-зависимая оптимизация программ
- •24 Организация информационных таблиц транслятора с хеш-адресацией
- •25 Методы разрешения коллизий в информационных таблицах с хэш-адресацией
- •Метод повторного хеширования (рехеширование)
- •Линейное рехеширование
- •Случайное рехеширование
- •Квадратичное рехеширование
- •Рехеширование – сложение
- •Метод цепочек
7. Алгоритмы внешней сортировки (вс)
При ВС требуется работать с данными, расположенными на внешних устройствах последовательного доступа. Для файлов, расположенных на таких устройствах в каждый момент времени доступен только одна запись последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов, где всегда доступен каждый элемент.
В основе большинства методов ВС лежит процедура слияния. Слияние означает объединение двух упорядоченных наборов данных в 1 упорядоченный набор с помощью повторяющихся действий по выбору доступных в данный момент элементов.
В процессе слияния поочередно сравниваются ключи в парах доступных в текущий момент записей из 2-х исходных наборов данных.
Запись с меньшим значением ключа помещается в результирующий набор данных и исключается из исходного. Действия повторяются, пока не будет исчерпан один из исходных наборов данных. Затем оставшиеся в другом наборе записи пересылаются в результирующий набор данных без изменения порядка их следования.
Покажем реализацию процедуры слияния для двух упорядоченных массивов
A[1..n] , B[1..m] в результирующий набор данных C[1.. n+m]
i, j, k – элементы в соответствующих массивах. Схема процедуры слияния:
Прямое слияние
Этот алгоритм – простейший алгоритм внешней сортировки, основанный на процедуре слияния последовательностей, называемых серией и представляющих собой упорядоченные подпоследовательности из записей файлов – серий.
Серия – несколько последовательно расположенных записей файла, упорядоченных по ключам.
Количество записей в серии называется ее длиной.
Последняя серия может иметь длину меньшую, чем остальные серии файлов.
Суть алгоритма прямого слияния заключается в след.
В исходном состоянии все n записей делятся на 2 файла t1, t2. считается, что каждый из этих файлов состоит из серии длины 1.
1. соответствующие серии файлов t1, t2 сливаются попарно и поочередно записываются в файлы g1, g2, организованные в виде серий удвоенной длины относительно t1, t2
После этого t1, t2 делаются пустыми.
2. соответствующие серии файлов g1, g2, попарно сливаются и поочередно записываются в t1, t2, организованные в виде серий удвоенной длины относительно g1, g2. После этого g1, g2 делаются пустыми.
3. Шаги 1 и 2 повторяются до тех пор, пока 1 из 2-х файлов в любой паре не станет пустым, тогда другой файл этой пары будет содержать единственную серию длины n, т.е. отсортированный исходный файл.
Замечание: на шаге 1 или 2 может оставаться одна серия без пары. Тогда она просто переписывается в соответствующий по очередности файл другой пары.
На каждом проходе (шаг 1 или 2) выполняется слияние серий с получением новых серий удвоенной длины и одновременно разделение на 2 файла.
После выполнения i подобных проходов получаем 2 файла состоящих из серий длины <=2i
Окончание процесса происходит при выполнении условия:
2i>=n
Следовательно, процесс сортировки прямым слиянием требует порядка log2n просмотров исходной последовательности.
А методы прямой сортировки требуют не меньше n проходов. Отсюда заметна более высокая скорость сортировки слияния даже по сравнению с прямыми методами сортировки.
Но, для сортировки массивов процедура слияния не используется, т.к. здесь требуется 2n ячеек памяти.
Естественное слияние
В случае прямого слияния частичная упорядоченность сортируемых данных не дает никакого преимущества. Это объясняется тем, что на каждом проходе сливаются серии фиксированной длины. При естественном слиянии (ЕС) длина серий не ограничивается, а определяется количеством элементов в уже упорядоченных подпоследовательностях выделяемых на каждом проходе.
ЕС начинается с образования 2-х файлов t1, t2. Для этого поочередно считываются записи ai исходной последовательности (неупорядоченной), которые записываются в файл t1 до тех пор, пока их ключи не убывают: f(ai)<=f(ai+1) (1). Если же f(ai)>f(ai+1) (2), то начиная с записи ai+1 формируется файл t2. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.
На некотором проходе алгоритма выполняется слияние пар серий из 2-х файлов аналогично прямому слиянию с записью результатов в другую пару файлов (g1 и g2). Но в отличие от прямого слияния длины сливаемых серий здесь не фиксированы, а определяются при выборе элементов из массивов с помощью рассмотренного условия. Пока выполняется условие (1) считается, что записи входят в одну серию, если (2), то начинается новая серия. Такие проходы выполняются до тех пор, пока один файл из какой-либо пары не станет пустым.
В процессе ЕС невозможно использовать алгоритм, применяемый для прямого слияния, т.к. при ПС количество серий в паре файлов может отличаться не более чем на 1. Последняя серия просто копируется. При ЕС такой подход может привести к потере данных, т.к. количество серий в сливаемых файлах может существенно отличаться (без пары могут остаться несколько серий).
Чтобы избежать возможной потери данных каждый проход должен завершаться копированием всех оставшихся без пар серий поочередно во вновь формируемые файлы:
Вычислительная сложность в сортировке ЕС в худшем случае оценивается аналогично прямому слиянию, но дает заметно лучший результат.
