15.Внешняя сортировка наборов данных
Внешняя сортировка — сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память, то есть применить одну из внутренних сортировок невозможно. Стоит отметить, что внутренняя сортировка значительно эффективней внешней, так как на обращение к оперативной памяти затрачивается намного меньше времени, чем к магнитным дискам, лентам…
Наиболее часто внешняя сортировка используется в СУБД(системы управления базами данных). Основным понятием при использовании внешней сортировки является понятие отрезка. Отрезком длины K является последовательность записей Ai, Ai+1,…,Ai+k, что в ней все записи упорядочены по некоторому ключу. Максимальное количество отрезков в файле N(все элементы не упорядочены). Минимальное количество отрезков 1(все элементы являются упорядоченными)
Например в некотором файле А есть одномерный массив: 12 35 65 0 24 26 3 5 84 90 6 2 30 Поделим массив на отрезки: 12 35 65|0 24 36|3 5 84 90|6|2 30 Можно сказать, что массив в файле А состоит из 5 отрезков.
Например в некотором файле B есть одномерный массив: 1 2 3 4 5 6 7 8 9 10 Поделим массив на отрезки: |1 2 3 4 5 6 7 8 9 10| Можно сказать, что массив в файле B состоит из 1 отрезков.
Например в некотором файле А есть одномерный массив: 20 17 16 14 13 10 9 8 6 4 3 2 0 Поделим массив на отрезки: |20|17|16|14|13|10|9|8|6|4|3|2|0| Можно сказать, что массив в файле А состоит из 13 отрезков.
Идея большинства методов заключается в расчленении данных на ряд последовательностей помещающихся в оперативную память. Далее применяется один из методов внутренней сортировки, после чего последовательности сливаются. Чем больше объём оперативной памяти, тем длиннее будут последовательности и, следовательно, тем меньшим окажется их количество, что увеличит скорость сортировки.
Если же объём оперативной памяти мал, то можно разделить исходные данные на несколько последовательностей, после чего непосредственно использовать процедуру слияния.
Основные методы сортировок: 1)Естественная сортировка(метод естественного слияния) 2)Сортировка методом двух путевого сбалансированного слияния 2.1)Сортировка методом n-путевого слияния. 3)Многофазная сортировка(Фибоначчиевая)
- 1. Классификация элементов и узлов эвм
- 2.Арифметические основы эвм. Типы данных, представление, перевод чисел коды чисел -пряиой обратный дополнительный
- 5. Методы адресации, выполнение команд, прерывания, переместимость.
- 6.Микропроцессоры, микро и мини эвм, ес эвм, семейства эвм[1,2]..............
- 7. Персональные эвм,обзор основных типов,аппаратные елементы
- 8. Организация наборов данных- методы доступа в наборах, записи, блоки, форматы [5,16].....
- 9. Фунции и состав типичной операционной системы, режимы работы
- 10 Основные команды операционной системы
- 11.Классификация структур данных, задачи обработки, массивы,.Списки
- 12.Древовидные и табличные структуры.
- 13.Методы поиска в массиве
- 14. Методы внутренней сортировки
- 15.Внешняя сортировка наборов данных
- 16.Жизненный цикл программы, тз..
- 17.Методы проектирования программ
- 18.Методы тестирования и отладки программ
- 19.Понятие о технологии программирования.Качество по
- 20.Классификация и основы построения по
- 21.Банки данных, архитектура бд
- 22.Субд и их функции.
- 23.Реляционная алгебра и обработка данных
- 24.Пакеты прикладных программ
- 25.Информационно-поисковые системы.
- 26.Системы искусственного интеллекта.Диалог с пользователем
- 27.Программная документация.
- 28.Основные понятия сапр-функциональное и системное наполнение
- 29.Локальные сети, протоколы
- 30.Основные методы решения уравнений
- 30.Основные методы решения уравнений
- 31.Квадратурные формулы, решение задачи Коши
- 32.Структурное программирование