Вторичное сравнение
Cтраница 1
 |
Просмотр 2 сортировки Шелла ( шаг 2.| Последний просмотр сортировки Шелла ( шаг1. [1] |
Вторичное сравнение между позициями 1 и 6 вызывает обмен между соответствующими элементами, в результате чего часть 1 становится упорядоченной. Все части теперь упорядочены. На рис. 3.1 в столбце 5 показан список к концу первого просмотра. [2]
Если первичное сравнение охватывает позиции 6 и 7, то цепочка вторичных сравнений может иметь самое большее пять сравнений. Этот максимум достигается, если исходный ключ из позиции 7 меньше всех ключей в списке, расположенных выше этой позиции. Фактическая длина последовательности вторичных сравнений зависит от величины двигающегося вверх элемента относительно величины каждого элемента из предшествующей упорядоченной части списка. [3]
Когда ключ - больше, чем ключ - шаг, то ключ; пересылается из своей позиции в свободную позицию, и метод начинает последовательность вторичных сравнений. Содержимое временной памяти ( ключ - шаг) - это запись, поднимающаяся на верх данной части. Ключ каждой записи сравнивается с временной памятью и, если обнаружено, что он больше, пересылается вниз списка в текущую свободную позицию. Каждая пересылка освобождает позицию перемещаемого элемента. Когда в списке обнаружен элемент с ключом. [4]
На рис. 2.5 указан обычный список из чисел. Теперь последовательность вторичных сравнений начинает продвигать ключ 6 вверх по списку, насколько это возможно. Поскольку клгачЗ меньше ключа 6, то обмен не выполняется, и вторичная последовательность кончается. Она окончилась бы в любом случае, так как при попытке продолжить эту последовательность была бы обнаружена вершина списка. [5]
Второй просмотр упорядочивает новые части тем же способом, что и первый просмотр. На рис. 3.2 показаны последовательности первичных и вторичных Сравнений, а также состояние списка в конце второго просмотра. Отметим, что этот метод не гарантирует, что при обменах элемент всегда перемещается ближе к нужной позиции. [6]
Назовем нисходящее сравнение первичным, а восходящее вторичным. Любое первичное сравнение может увеличить число вторичных сравнений. [7]
Если первичное сравнение охватывает позиции 6 и 7, то цепочка вторичных сравнений может иметь самое большее пять сравнений. Этот максимум достигается, если исходный ключ из позиции 7 меньше всех ключей в списке, расположенных выше этой позиции. Фактическая длина последовательности вторичных сравнений зависит от величины двигающегося вверх элемента относительно величины каждого элемента из предшествующей упорядоченной части списка. [8]
Если каждое первичное сравнение вызывает обмен, то имеем максимальное число обменов. Так как ожидается приблизительно Л / 2 / 4 вторичных сравнений, то можно ожидать примерно N2 ( 4 обменов. [9]
В койце второго просмотра части переопределяются вновь. Шаг опять сокращается до половины предыдущего шага. Последний просмотр в сортировке Шелла всегда имеет шаг, равный 1, и является простым просеиванием. На рис. 3.3 показаны последовательности первичных и вторичных сравнений в процессе завершения упорядочения списка. [10]
Изучение влияния ширм было продолжено для установления связи между направлением входящего потока загрузки и требованиями к качеству топлива. Всасывающий клапан закреплялся в желаемом положении таким образом, что ширмы располагались так, как показано на фиг. Здесь видно, что направление входящего потока значительно влияет на требования к моторным свойствам топлив. Однако во всех случаях независимо от направления потока клапаны с ширмами дали лучшие результаты. Вторичное сравнение мощности на границе детонации, проведенное на 70-октановом топливе, показало, что выигрыш в требованиях к октановой характеристике топлив не сопровождается снижением мощности. [11]
Страницы: 1