Внутренняя сортировка
Cтраница 3
Одна из первых попыток машинной сортировки была предпринята Джоном фон Нейманом, который запрограммировал внутреннюю сортировку слиянием ( упр. [31]
 |
Десятичные числа с пятеричным эквивалентом. [32] |
Когда группа настолько мала, что может поместиться в памяти, этот процесс можно оборвать внутренней сортировкой. [33]
Используя операторы вставления и удаления списков, ЗУ со списочной организацией позволяет также эффективно провести операцию внутренней сортировки информации по какому-либо признаку. Сущность сортировки в этом случае заключается в установлении связей между неподвижными элементами сортируемого массива. [34]
При недревовидном разрядном упорядочении сегменты последовательности данных, передаваемые между внутренней и внешней памятью, не связаны с внутренней сортировкой последовательности, а все этапы разделения записей на группы, число которых определяется разрядностью признака, являются этапами переписи данных во внешнюю память. [35]
При многофазной сортировке одно устройство остается свободным, а на других в виде строк различной длины распределяется с помощью ряда внутренних сортировок весь набор данных. Длины строк, размещенных на отдельных устройствах, зависят от общего количества элементарных строк и могут быть-вычислены в виде так называемых чисел Фибоначчи. Процесс слияния строк на свободном устройстве продолжается до тех пор, пока не окажется, что. Затем слияние снова продолжается, причем в качестве выходного устройства используется только что освободившееся, а другие устройства - в качестве входных. И далее каждый раз, когда одно из устройств освобождается, оно начинает использоваться в качестве выходного. Процесс заканчивается, когда будут слиты все строки. [37]
Оператор MERGE ( СЛИТЬ) совершенно не связан с оператором SORT, хотя отмечалось, что при выполнении оператора SORT сначала производится внутренняя сортировка, а затем слияние. Однако слияние при сортировке применяется только к рабочим файлам и не может управляться программистом. Оператор MERGE введен специально для того, чтобы дать программисту возможность объединять файлы, которые уже были отсортированы в соответствии с определенными ключами. [38]
Если внутренняя сортировка есть, то ее эффективность зависит от того, насколько мала должна быть группа, чтобы ее можно было подвергнуть внутренней сортировке. Внутренняя сортировка сокращает количество просмотров ключей, исключая распределение по последним разрядам. [39]
В этом разделе мы обсуждаем два типа обменных сортировок: хорошо известную, но относительно неэффективную пузырьковую сортировку и быструю сортировку - один из лучших со всех точек зрения алгоритмов внутренней сортировки. [40]
Библиотека стандартных программ ( БСП) Минск-32 содержит сотни стандартных программ, ориентированных на решение различных задач: перевод чисел из одной системы счисления в другую, редактирование информации, обработка данных, корректировка массивов, внутренняя сортировка, выборка, слияние и внешняя сортировка информации, решение задач линейного программирования, решение задач сетевого планирования, элементарные и специальные функции действительного, чисто мнимого и комплексного аргумента, программированная арифметика, вычисление корней алгебраических и транс-цедентных уравнений, операции с матрицами и векторами, вычисление определителей и решение систем линейных алгебраических уравнений, определение характеристического полинома, собственных значений и собственных векторов матрицы, численное решение обыкновенных дифференциальных уравнений, численное интегрирование, интерполяция и аппроксимация функций, специальные функции действительного и чисто мнимого аргумента, минимизация функции многих переменных, решение задач математической статистики. [41]
Если внутренняя сортировка есть, то ее эффективность зависит от того, насколько мала должна быть группа, чтобы ее можно было подвергнуть внутренней сортировке. Внутренняя сортировка сокращает количество просмотров ключей, исключая распределение по последним разрядам. [42]
 |
Блок-схема подпрограммы внутренней сортировки линейного выбора с обменом ( подпрограмма SORT. [43] |
Для реализации метода используются две дополнительные ячейки: Т, в которую заносится значение текущего элемента сортируемого массива, и / МАХ-порядковый номер этого элемента. Рассмотрим блок-схему алгоритма внутренней сортировки линейного выбора с обменом ( рис. 38): предположим, что на / - м шаге алгоритма упорядочено / - - 1 предыдущих элементов. Тогда для определения / - го элемента упорядоченной последовательности выбирается максимальный элемент с номером, изменяющимся в пределах от / до NР, где NP - число элементов, подлежащих упорядочению. [44]
Виртуальная память отличается от других видов памяти как поддерживающей аппаратурой, так и операционной системой, под управлением которой осуществляется работа с ней. Во-первых, даже при внутренней сортировке в виртуальной памяти реальная обработка выполняется с использованием внешней памяти, поэтому необходимо учитывать ее влияние - неизбежные при этом затраты на запись и считывание. И наоборот, считывание и запись при внешней сортировке почти идентичны перемещениям записей в виртуальной памяти. Из соображений практического удобства обычно гораздо охотнее используют внутреннюю сортировку. При этом важным фактором, влияющим на эффективность, является интенсивность использования массы сильно различающихся адресов за сравнительно короткие временные интервалы. [45]
Страницы: 1 2 3 4