Осциллирующей сортировки

В случае осциллирующей сортировки (рис 9.20) при первом просмотре, используя методику выбора с замещением, равномерно распределяют на трех отдельных устройствах элементарные рассортированные строки. Затем, применяя предыдущий метод, эти строки объединяют на четвертом устройстве. Эта „процедура повторяется дважды, причем всегда одно из устройств освобождается для последующего слияния. Таким образом, после завершения всей операции на каждом из трех устройств будет размещено по одной рассортированной строке, состоящей из трех элементарных строк. Каждая из них в три раза длиннее, чем строки, получаемые с помощью внутренней сортировки. (Если при внутренней сортировке используется методика замещения, то такое утверждение верно только приблизительно.) Эти удлиненные строки снова сливаются в одну строку на пустом устройстве, и процесс опять повторяется сначала. Всякий раз, когда все строки, размещенные на трех внешних устройствах, состоят из одинакового количества элементарных строк, получаемых посредством внутренней сортировки, эти удлиненные строки снова сливаются в одну строку на четвертом устройстве.

Такое распределение и слияние продолжаются до тех пор, пока на одном из устройств не будет сформирован файл, состоящий из одной рассортированной строки. Если для временного хранения строк используются магнитные ленты, то перемотка лент займет много времени.

Сортировку можно ускорить, если ленты можно читать также и в обратном направлении. (Такого рода возможность обеспечивается многими лентопротяжными устройствами.) После фазы распределения ленты, на которые только что была произведена запись, находятся в конце рассортированных строк и могут быть просмотрены в режиме обратного чтения. Одновременное этим можно установить (перемотать) в требуемое положение ленту, предназначенную для слияния рассортированных строк таким образом, исключаются дополнительные перемотки магнитных лент. Естественно, когда выполняется обратное чтение, возрастающий порядок следования элементов заменяется на убывающий.

Принцип осциллирующей сортировки можно проследить, обратившись к рис. 9 21. Числа, расположенные под именами устройств, указывают выраженные через количество составляющих элементарных .строк длины строк на устройствах и порядок следования
элементов в этих строках. Например, перед вторым шагом ленты Л, В и С находятся в конце первой рассортированной строки, а D — в начале, т. е. в точке загрузки. Затем ленты Д В й С читаются в обратном направлении и содержащиеся на них строки сливаются на ленте D в строку длиной в три элементарные строки, представленную в убывающем порядке. На третьем шаге к этой строке будет добавлена представленная уже в возрастающем порядке рассортированная строка длиной в одну элементарную строку.


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