Пример 2. Пусть задана линейная таблица А, элементы которой нумеруются от К до N (К < N).Построим алгоритм поиска наименьшего элемента линейной таблицы

Пусть задана линейная таблица А, элементы которой нумеруются от К до N (К < N). Построим алгоритм поиска наименьшего элемента линейной таблицы. В этом алгоритме элементы таблицы будут просматриваться по порядку, от первого до последнего. Для этого будет использоваться переменная i — номер первого непросмотренного элемента таблицы. Кроме i, будут использоваться еще две переменные: МИН — «минимум из уже просмотренных элементов»; L — «номер элемента, минимального среди уже просмотренных».

Работа алгоритма начинается с серии команд, в которой мы присваиваем переменной МИН значение начального элемента таблицы. Этот элемент уже просмотрен, и мы берем К в качестве значения для l; просмотрен один элемент А [ К ],и он минимален среди просмотренных. Берем K + 1 в качестве значения для i — номера первого непросмотренного элемента.

Работа алгоритма завершается, когда вся таблица просмотрена, и номер ее минимального элемента найден. Этот номер и является результатом.

Алгоритм имеет следующий вид:

алг МИНЭЛЕМЕНТ (цел К, N, вещтаб А [ К: N ], цел l)

арг А, К, N

рез l

начцел i, вещ МИН

МИН:= А [ К ]; l:= К; i:=K + 1

пока i < N

нц

если MИH:= A [ i ]

то МИН:= А [ i ]; l:= i

Все

i:= i + 1

кц

Кон

Построим теперь алгоритм упорядочения линейной таблицы, используя алгоритм МИНЭЛЕМЕНТ в качестве вспомогательного. Задача упорядочения таблицы формулируется следующим образом. Пусть задана линейная таблица С, элементы которой нумеруются от п до М (п <.М): вещтаб С [ п: М ].

Необходимо переставить элементы этой таблицы так, чтобы они шли в порядке возрастания. Идея алгоритма упорядочения состоит в следующем. Применив алгоритм МИНЭЛЕМЕНТ к таблице С [ п: М ], мы определим номер l элемента этой таблицы, имеющего наименьшее значение. После этого поменяем значения элементов С [ п ]и С [ I ]. Тогда на n -м месте таблицы С окажется самый маленький по величине элемент. На следующем шаге применяем алгоритм МИНЭЛЕМЕНТ к таблице С [ п + 1: М ]и снова определяем номер l минимального элемента этой таблицы. Поменяем местами элементы С [ п + 1 ] и С [ l ], тогда на п + 1-м месте окажется самый маленький из оставшихся элементов. Далее будем применять алгоритм МИНЭЛЕМЕНТ к таблицам С [ п + 2: М], С [ п + 3: М ],......, С [ М − 1, М ] и менять местами элементы С [п + 2] и С [ l ], С [ n + 3] и С [ l ] и, наконец, С [М − 1] и С [ l ]. В результате таблица С окажется упорядоченной.