Пример итеративной обработки массива

Рассмотрим итерационный способ сортировки элементов одномерного числового массива в порядке возрастания, суть которого заключается в следующем. Просматривая массив, будем менять местами его соседние элементы в тех случаях, когда они нарушают требуемый порядок, иными словами, больший элемент оказывается в положении с меньшим индексом. Очевидно, что каждая такая перестановка “соседей” с позиций сортировки улучшает ситуацию в массиве, но одного “прохода вдоль массива” скорее всего будет недостаточно. Максимальное число просмотров равняется количеству элементов массива без единицы, что достигается при наиболее неудачной начальной расстановке (когда самое маленькое число стоит последним). Тем не менее вполне возможны ситуации, когда требуемый порядок по указанному алгоритму удастся получить за меньшее число проходов; в частности, в предельном случае, когда массив уже упорядочен, в этом можно убедиться единичным просмотром.

Каждый просмотр массива, приближающий к решению поставленной задачи (причем результат обработки всегда служит начальным состоянием для нового просмотра), в компьютерной литературе называют итерацией. В словаре [3], например, дается такое определение данного термина: итерация — это “повторение пошагового процесса, когда результат предыдущего шага (шагов) используется для получения результата следующего шага”.

Вообще говоря, любой цикл обработки массивов есть итерация. Правда, как правило, итерационными алгоритмами чаще всего называют такие, в которых количество повторений заранее неизвестно. Наш алгоритм сортировки является именно таким.

Механизм сортировки описанным методом настолько широко известен, что здесь мы приведем только возможное решение на Паскале и совсем краткие пояснения к нему.

PROGRAM sort_iter(INPUT, OUTPUT);

CONST n = 10;

m:ARRAY [1..n] OF INTEGER =

(10,9,8,7,6,5,4,3,2,1);

VAR i,p: INTEGER; c: BOOLEAN;

BEGIN REPEAT c:= FALSE;

FOR i:= 1 TO n - 1 DO

IF m[i] > m[i + 1] THEN

BEGIN p:= m[i]; m[i]:= m[i + 1];

m[i + 1]:= p;

c:= TRUE

END;

FOR i:= 1 TO n DO

WRITE(m[i],' '); WRITELN;

UNTIL NOT c;

END.

В программе в виде типизированной константы задан массив, который с точки зрения сортировки по возрастанию представляет наибольшую трудность. Итерационный процесс сортировки регулируется переменной c, которая имеет смысл наличия произведенных во время итерации перестановок: когда c после выполнения очередной итерации ложно, перестановок не было и сортировку можно прекратить. Первый из циклов FOR обеспечивает проход по массиву и обмен “неправильно стоящих” соседних элементов местами, а второй — служит для контрольного вывода на экран результатов каждой итерации сортировки.

Заметим, что в билете № 5 в связи с рассмотрением физической задачи о расчете распределения температуры в стержне также был подробно описан пример итерационного алгоритма обработки одномерного массива.

Дата добавления: 2015-04-23