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

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

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

Источник: delete-it