Краткие итоги
Ключевые термины
Внешняя сортировка – это сортировка данных, которые расположены на внешних устройствах и не вмещающихся в оперативную память.
Двухпутевое слияние – это сортировка, в которой данные распределяются на два вспомогательных файла.
Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние.
Длина серии – это количество элементов в серии.
Естественное слияние – это сортировка, при которой всегда сливаются две самые длинные из возможных серий.
Многопутевое слияние– это сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.
Несбалансированное слияние – это естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга более чем на единицу.
Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.
Простое слияние – это одна из сортировок на основе слияния называется, в которой длина серий фиксируется на каждом шаге.
Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.
Сбалансированное слияние – это естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу.
Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу.
Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов доступных в данный момент.
Фаза – это действия по однократной обработке всей последовательности элементов.
1.Внешние сортировки применяются к данным, которые хранятся во внешней памяти. Внешние сортировки применяются, если объем сортируемых данных превосходит допустимое место в ОЗУ.
2.Внешние сортировки, по сравнению с внутренними, характеризуются проигрышем по времени за счет обращения к внешним носителям.
3.К наиболее известным алгоритмам внешних сортировок относятся: сортировки слиянием (простое слияние и естественное слияние); улучшенные сортировки (многофазная сортировка и каскадная сортировка).
4.Алгоритмы внешних сортировок отличаются по реализации числом фаз и путей.
5.Простое слияние является одной из сортировок на основе слияния, в которой длина серий фиксируется на каждом шаге.
6.Естественное слияние является сортировкой, при которой всегда сливаются две самые длинные из возможных серий.
7.Число чтений или перезаписей файлов при использовании метода естественного слияния будет не хуже, чем при применении метода простого слияния, а в среднем – даже лучше. Однако в данном методе увеличивается число сравнений за счет распознавания концов серий.