Cтраница 4
Эта техника получила название пузырьковой сортировки, так как большие элементы пузырьками всплывают вверх в конец списка. Реализация метода представлена алгоритмом 5.2. В алгоритме используется переменная 6, значение которой при каждом проходе цикла устанавливается равным наибольшему индексу t, такому, что все элементы дм, д / 2 - ап У находятся на своих окончательных позициях. Ясно, что не имеет смысла продолжать просмотр для указанных элементов. [46]
Наиболее очевидный метод систематического обмена местами имен с неправильным порядком состоит в просмотре пар смежных имен последовательно слева направо и перемене мест тех имен, которые не отвечают порядку. В алгоритме 7.2 эта простая идея реализуется с одним небольшим усовершенствованием: ясно, что не имеет смысла продолжать просмотр для больших имен ( в правом конце таблицы), про которые известно, что они находятся на своих окончательных позициях. [47]
Программа 10.1 представляет полную реализацию этого метода. Применяемый в ней процесс разбиения по существу лишь немногим отличается от разбиения, реализованного в программе 7.2, за исключением того, что в рассматриваемом случае в качестве разделяющего элемента используется число 2й, а не некоторый ключ из файла. Поскольку числа 2й может и не быть в файле, то нет гарантии того, что конкретный элемент будет помещен в свою окончательную позицию в процессе разбиения. Рассматриваемый алгоритм отличается от алгоритма быстрой сортировки, поскольку рекурсивные вызовы выполняются для ключей, имеющим на 1 бит меньше. Это различие существенно влияет на эффективность алгоритма. Например, если имеет место вырожденное разбиение файла из N элементов, то произойдет рекурсивный вызов для подфайла размером N для ключей, имеющим размер на 1 разряд меньше. Следовательно, число таких вызовов ограничено количеством разрядов в ключе. В противоположность этому, последовательное использование разделяющих значений, взятых не из самого файла в условиях стандартной быстрой сортировки может привести к возникновению бесконечного рекурсивного цикла. [48]
В процессе пузырьковой сортировки ключи с малыми значениями устремляются влево. Поскольку сортировка производится в направлении справа налево, каждый ключ меняется местами с ключом слева до тех пор, пока не будет обнаружен ключ с меньшим значением. На первом проходе Б меняется местами с L, P и М, пока не остановится справа от А; далее уже А продвигается к началу файла, пока не остановится перед другим А, который уже занимает окончательную позицию, 1 - й по величине ключ устанавливается в свое окончательное положение после i-ого прохода, как и в случае сортировки выбором, но при этом и другие ключи также приближаются к своим окончательным позициям. [49]
В процессе пузырьковой сортировки ключи с малыми значениями устремляются влево. Поскольку сортировка производится в направлении справа налево, каждый ключ меняется местами с ключом слева до тех пор, пока не будет обнаружен ключ с меньшим значением. На первом проходе Б меняется местами с L, P и М, пока не остановится справа от А; далее уже А продвигается к началу файла, пока не остановится перед другим А, который уже занимает окончательную позицию, 1 - й по величине ключ устанавливается в свое окончательное положение после i-ого прохода, как и в случае сортировки выбором, но при этом и другие ключи также приближаются к своим окончательным позициям. [50]
Убедимся сначала в том, что относительно утверждения ( Ь) нельзя ожидать ничего большего. Для этого рассмотрим локально конечную игру с дискретными выигрышами, к которой мы добавим одну или несколько позиций, из которых нельзя достичь никакой окончательной позиции. Первоначальная игра обладает функцией решения. Если мы поставим в соответствие добавленным позициям произвольно одну и ту же окончательную позицию, то получим функцию решения расширенной игры. [51]
Движения по диагонали не допускаются. Обычно требуют, чтобы последний колышек находился в центральном отверстии. Любой, кто достаточно много играет в солитер, заметит, что, если и не требовать, чтобы последний колышек оказался в центре, представляется маловероятным, чтобы он мог оказаться в любом другом месте. Существует ограниченное число окончательных позиций. [52]