Другие методы упорядочения в оперативном запоминающем устройстве

17-08-2013, 17:04
Просмотров: 1544
Сивард приводит сведения по другим методам упорядочения информации. Ставится задача - найти наименьший элемент из элементов и записать его; затем найти наименьший из оставшихся, записать его и продолжать этот процесс до тех пор, пока не будет закончен перебор всех элементов. Число сравнений равно. Осуществляется сравнение всех пар последовательных элементов, начинающихся с нечетного номера,. и, если требуется, выполняется их перестановка. Процесс повторяется, но для всех пар, начинающихся с четного элемента. Тот и другой процесс выполняется попеременно до тех пор, пока не прекратятся перестановки.

Другие методы упорядочения в оперативном запоминающем устройстве


Осуществляется последовательное сравнение элементов информации и их сдвиг вперед, до тех пор, пока не будет найден элемент с меньшим значением ключа. Последовательность упорядочена, когда просмотрен последний элемент информации. Число сравнений при наиболее неблагоприятном исходном варианте равно
Элементы сравниваются и переставляются, если это требуется. Процесс повторяется до тех пор, пока перестановки прекратятся. Опять-таки число перестановок. Для начала делается допущение, что при каждом обращении записывается или считывается один элемент информации.
1. Исходная последовательность (в данном случае записанная на двух лентах) подготавливается и записывается на две выходные ленты.
2. Материал с этих двух выходных лент, рассматриваемых теперь как входные, объединяется и результат записывается на две другие выходные ленты. Процесс повторяется до завершения.
Таким образом, оценка числа сравнений, полученная для методов упорядочения сортировкой или объединением, пока наилучшая. За исключением крайне редких случаев, когда заранее известен характер упорядоченности последовательности, следует пользоваться этими двумя методами.

Источник: delete-it
Автор: Николай Максименко
Опубликовано пользователем: 805 (смотреть все)
Комментарии:
» » » Другие методы упорядочения в оперативном запоминающем устройстве