Метод смежных пар

Алгоритм, реализующий метод смежных пар, основан на сравнении двух соседних чисел с последующей их перестановкой в случае, если они расположены не в требуемой очередности.

На рис.9.1 приведен алгоритм сортировки заданного ряда чисел по возрастанию. Для регулярного сравнения двух соседних чисел предусматривается циклический процесс. В заголовке цикла, в качестве параметра цикла, используется адрес числа с его областью изменения от до k = . Здесь следует обратить внимание на то, что правая граница области изменения параметра цикла i равна не n, а n-1. Это объясняется тем, что при сравнении двух соседних чисел адрес первого числа определяется значением параметра цикла i, а адрес второго числа вычисляется добавлением единицы (i+1). Если бы параметр цикла имел бы свое последнее значение n, а не n-1, то при i = n адрес второго числа определялся бы как i= n+1, а это уже выходит за пределы рассматриваемого ряда, и числа с таким адресом нет. Поэтому, чтобы исключить такую ситуацию, последнее значение параметра цикла принимается на единицу меньше.

В теле цикла происходит сравнение значений двух соседних чисел и , и в случае их неправильного расположения осуществляется их взаимная перестановка с помощью промежуточной переменной . Переменная используется с целью исключения потери значения одного из чисел при перестановке. Факт перестановки фиксируется с помощью переменной , которая играет роль индикатора, путем установки ей значения равной единице. Если же числа расположены в требуемой очередности, то их перестановка не производится. После завершения каждого цикла, на последнее место перемещается самое большое число из чисел, рассматриваемых в этом цикле. Кроме этого, проверяется состояние индикатора .

 

 

 

–

 

+

–

 

Рис. 9.1 Блок – схема сортировки чисел по возрастанию

Если его значение равно единице, то это означает, что хотя бы одна перестановка в завершившемся цикле была, и, следовательно, необходимо совершить еще один цикл для сравнения соседних чисел, но без последнего числа, которое и так уже расположено на нужном месте. Исключение последнего числа из рассмотрения, после завершения очередного цикла, осуществляется операцией k = k –1. Это позволяет экономить машинное время, так как нет никакого смысла проверять размещение уже расположенного на нужном месте числа.

После этого все начинается сначала. Индикатор устанавливается в стартовое состояние со значением нуль, и в цикле производится поочередное сравнение двух соседних чисел. Такие циклы будут повторяться до тех пор, пока не обнаружится, что после завершения очередного цикла индикатор не поменял своего начального значения 0 на 1. И это будет означать, что в процессе циклической операции не было ни одной перестановки, а, следовательно, числа расположились в требуемой последовательности, то есть ряд отсортирован. Таким образом, алгоритм позволяет повторять циклические операции столько раз, сколько будет необходимо для завершения процесса сортировки.

Сортировка ряда чисел по убыванию выполняется аналогично. В этом случае в блок-схеме следует выполнить некоторые изменения. Так в операции сравнения соседних чисел необходимо знак " > " заменить знаком " < ".

Метод смежных пар экономичен с точки зрения расхода машинного времени. Если исходный ряд уже сортирован в требуемой последовательности, то достаточно выполнить только один проверочный цикл, чтобы убедиться, что индикатор не поменял своего начального значения 0.

9.1.2. Метод поиска наименьшего (наибольшего)

Идея метода состоит в том, что определяется место наименьшего числа при сортировке ряда по возрастанию (наибольшего числа при сортировке по убыванию), которое затем меняется местами с первым числом ряда. После этого ряд чисел рассматривается уже без первого числа. Найденное наименьшее (наибольшее) число выставляется аналогичным образом на второе место и в дальнейшем ряд чисел рассматривается уже без двух первых чисел, которые выставлены в нужном порядке. Это повторяется многократно до тех пор, пока останется одно число, после чего процесс сортировки прекращается.

На рис.9.2 приведен алгоритм сортировки чисел по возрастанию. Блок – схема представлена двумя вложенными циклами. Внешний цикл с параметром цикла k осуществляет назначение каждый раз числа на роль минимального a_min в рассматриваемом ряде чисел и одновременно отсекает уже выставленное вперед число после предыдущего цикла.

Вложенный цикл с параметром цикла i представляет собой типовой алгоритм определения наименьшего числа из ряда чисел. Здесь роль наименьшего числа играет число , которое изменяется последовательно от a₁ до a_n-1. Вложенный цикл рассматривает ряд чисел, начиная с соседнего с , то есть с числа . За пределами вложенного цикла производится обмен числами, наименьшего и первого в рассматриваемом ряде. Здесь роль переменной , используемой в методе смежных пар, играет переменная

Если в роли минимального числа ряда осталось первое число a_k, то обмен не нужен. Этот факт устанавливается проверкой условия .

 

 

 

 

 

Рис. 9.2 Блок – схема сортировки чисел по возрастанию методом определения наименьшего числа

В отличие от предыдущего метода, этот алгоритм осуществляет сортировку чисел по «жесткой» программе. То есть, независимо от того, сортирован ли исходный ряд или нет, тело внешнего цикла будет выполнено раз. В этом случае непроизводительно расходуется машинное время, что определяет недостаток метода. Но, тем не менее, этот метод имеет свою область применения. Таким методом удобно решать задачи по определению нескольких (больше одного) минимальных чисел ряда. В этом случае достаточно установить правую границу параметра внешнего цикла k не n-1, а то число, которое определяет количество искомых минимальных элементов ряда.

Сортировка по убыванию осуществляется аналогично. При этом в рассмотренной блок-схеме идентификатор необходимо заменить идентификатором , что вызывает правильные ассоциации, а операцию сравнения " < " – на операцию " > ".