Внешняя сортировка - это термин для обозначения класса алгоритмов сортировки, которые могут обрабатывать огромные объемы данных. Внешняя сортировка необходима, когда сортируемые данные не помещаются в основную память вычислительного устройства (обычно оперативную) и вместо этого должны находиться в более медленной внешней памяти (обычно на жестком диске).
Внешняя сортировка обычно использует гибридную стратегию сортировки-слияния. На этапе сортировки фрагменты данных, достаточно маленькие, чтобы поместиться в основной памяти, считываются, сортируются и записываются во временный файл. На этапе слияния отсортированные подфайлы объединяются в один большой файл.
Внешняя сортировка — это метод хранения данных во вторичной памяти, загрузки данных по частям в основную память и последующей сортировки их там. Внешняя сортировка так названа, поскольку предназначенв для освобождения буфера памяти при работе с внешними устройствами. Отсортированные данные хранятся в промежуточных файлах. Наконец, эти файлы объединяются для получения отсортированных данных. Таким образом, методы внешней сортировки упрощают сортировку больших объемов данных. Для внешней сортировки невозможно поместить все данные в одну память. В этом случае часть памяти должна храниться на таких носителях, как жесткие диски или компакт-диски.
Требования внешней сортировки возникают, когда данные, которые необходимо хранить в основной памяти, не помещаются. Фактически следование за ним состоит из двух фаз.
Этап сортировки: на этом этапе большой объем данных сортируется в промежуточный файл.
Этап слияния: на этом этапе отсортированные файлы объединяются в один большой файл.
Одним из лучших примеров внешней сортировки является внешняя сортировка слиянием. Внешняя сортировка слиянием — это метод, при котором данные хранятся в промежуточных файлах, каждый промежуточный файл сортируется отдельно и объединяется или объединяется для получения отсортированных данных.
Пример: Предположим, вы хотите отсортировать 10 000 записей. Для этого нам нужно применить внешний метод сортировки слиянием. Предположим, что основная память способна хранить 500 записей на блок, а размер каждого блока равен 100 записям.
Двунаправленная сортировка слиянием — это метод, который работает в два этапа, описанных ниже.
Этап 1: Сначала разделите записи на блоки, затем используйте две входные ленты для перестановки отдельных записей.
Этап 2: На этом этапе отсортированные блоки объединяются и создается один отсортированный файл с использованием двух выходных лент.
Таким образом, мы можем сказать, что двунаправленная сортировка слиянием использует две входные ленты и две выходные ленты для сортировки данных.
Алгоритм двусторонней сортировки слиянием:
Шаг 1) Разделите элементы на блоки размером M. Отсортируйте каждый блок и запишите его на диск.
Шаг 2) Объедините два прогона
Прочитайте первое значение в каждом из двух прогонов.
Затем сравните и отсортируйте их.
Запишите отсортированные записи на выходную ленту.
Шаг 3) Повторите шаг 2, чтобы увеличить прогон с чередованием лент. Наконец, мы получаем один отсортированный список.
Анализируя вторичные источники по теме внешней сортировки, можно отметить, что наиболее распространена простая сортировка слиянием [ 1]. В нем количество сравнений и перестановок оценивается как O (nlog (n)). Однако он не учитывает тот факт, что последовательность уже может быть частично упорядочена [1 ]. Тот же автор отмечает, что такая внешняя сортировка, как многофазное слияние дает ожидаемый результат, объединяя максимальное количество рядов на каждом этапе, если начальное распределение рядов на вспомогательном файле описывается соседними числами Фибоначчи [1] .
#сортировка
#программирование
#данные
#россиястранавозможностей
#код
#наука
#алгоритмы
#бизнес
