programmingSimilar presentations:
Внешние сортировки
1.
Внешниесортировки
2.
Когда обычные сортировки несправляются?
Когда данных слишком много, а оперативной памяти не хватает, на
помощь приходят внешние сортировки. Они помогают работать с огромными
файлами, например, в базах данных
Все данные уместились в оперативной
памяти компьютера
Данные не умещаются и поступают
частями
3.
Основные понятияВнешняя сортировка — сортировка данных, расположенных на
периферийных устройствах и не вмещающихся в оперативную память, то есть
когда применить одну из внутренних сортировок невозможно.
Серия – это кусочек данных, который уже отсортирован. Внешние
сортировки работают с такими сериями, чтобы быстрее получить итоговый
порядок.
4.
Как работает внешняя сортировка?Есть два ключевых процесса:
1. Распределение – разбиение данных на части.
2. Слияние – объединение частей в один отсортированный массив.
5.
Распределение• Данные разбиваются на серии, где каждая серия отсортирована.
• Каждая серия записана в отдельный файл.
6.
Слияние• Серии из файлов объединяются попарно.
• Получается новая отсортированная серия.
7.
Основные методы сортировокЕстественная сортировка - метод естественного слияния
Сортировка методом двух-путевого сбалансированного слияния
Многофазная сортировка – на основе ряда чисел Фибоначчи.
8.
Естественное слияние – когда природапомогает!
В исходных данных уже могут быть участки, где элементы идут в
порядке возрастания или убывания. Поэтому алгоритм использует уже
упорядоченные серии. Мы объединяем их, пока весь файл не будет
отсортирован.
Алгоритм:
1. Деление на серии.
2. Слияние серий воедино с сортировкой.
9.
Алгоритм10.
Работа алгоритма11.
Сбалансированное слияние – какупорядочить хаос?
Алгоритм использует два файла и чередует их роли. Это
помогает равномерно объединять серии.
•Данные разбиваются на две равные части (или почти равные, если
количество элементов нечётное).
•Отсортированные части объединяются в один упорядоченный массив.
•Каждая часть рекурсивно сортируется.
12.
Алгоритм13.
Работа алгоритма14.
Работа алгоритма15.
Работа алгоритма16.
Работа алгоритма17.
Работа алгоритма18.
Многофазная сортировка – хитраястратегия!
Многофазная сортировка — это метод внешней сортировки, который
используется для упорядочивания данных, не помещающихся в оперативную
память. Этот метод основан на распределении данных по нескольким файлам
и их последовательном слиянии с использованием фиктивных серий для
оптимизации процесса.
Чтобы быстрее объединять серии, их распределяют неравномерно – по
числам Фибоначчи. Если серий не хватает, добавляют пустые (фиктивные)
серии.
19.
Принцип работы1. Начальное распределение серий
• Исходные данные разбиваются на серии и распределяются по нескольким файлам.
• Количество серий в каждом файле должно соответствовать определённой
последовательности (например, числам Фибоначчи).
2. Слияние серий
• Серии из нескольких файлов сливаются в один, при этом на каждом этапе количество
серий уменьшается.
• Фиктивные серии используются для балансировки процесса.
3. Повторение процесса
• Процесс слияния повторяется до тех пор, пока не останется одна полностью
отсортированная серия.