Организация данных и структуры данных
Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора |
Общее про методы сортировкиСортировка — это одна из процедур, наиболее часто используемых при обработке деловых данных. Для того чтобы эффективно обрабатывать многотомные массивы данных и получать результаты в удобочитаемой форме, необходимо рассортировать данные в соответствии с неким правильно выбранным критерием. Кроме того, методы сортировки часто бывают необходимы для организации данных во внутренней памяти машины. Сама операционная система, компиляторы языков высокого уровня и ассемблеры, списковые процессоры — все они используют некоторый алгоритм сортировки при построении различных внутренних таблиц. С основными принципами и методами сортировки можно детально ознакомиться, обратившись к работам [23, 24]. Сначала данные сортируются в соответствии с наивысшим по приоритету ключом, затем в пределах упорядоченной таким образом последовательности осуществляется сортировка согласно значением следующего по приоритету ключа и т. д. Примером такого упорядочивания может служить телефонный справочник, где старшим ключом критерия сортировки является фамилия, а следующим ключом — имя абонента. Так же как и в случае любой машинной задачи, при реализации процесса сортировки мы сталкиваемся с противоречиями между временем обработки и объемами основной и внешней памяти, а также между капитальными затратами на оборудование и стоимостью его эксплуатации. Для того чтобы быстро сортировать большие массивы данных, необходимо иметь много места в основной памяти и много периферийных устройств (магнитных лент, дисков, барабанов), а это все дорогостоящее оборудование. С другой стороны, когда используется небольшой объем основной памяти и немного периферийных устройств, увеличивается время сортировки. А машинное время также стоит дорого. Для того чтобы при имеющихся в распоряжении ресурсах выполнить сортировку за разумное время, ее, как правило, реализуют в несколько шагов. Поскольку выполнение операций в основной памяти происходит значительно быстрее, чем выполнение операций чтения данных из периферийных устройств или записи в такие устройства, то часть данных считывается в основную память и там сортируется. Затем такой рассортированный подфайл (последовательность), называемый элементарной или единичной строкой, временно размещается на диске или ленте, а следующая часть исходного файла считывается в основную память для сортировки и т. д. В конце концов рассортированные подфайлы, временно хранящиеся во внешней памяти, за несколько шагов сливаются в один файл. Если речь идет о небольшом количестве данных, то их можно все за один шаг рассортировать в основной памяти, однако при сортировке большого файла всегда приходится использовать такие внешние запоминающие устройства, как барабаны, магнитные ленты или диски. Следовательно, эффективность сортировки зависит от двух факторов: |