7. Алгоритмы нахождения наибольшего и наименьшего значения

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

Пример. Сформировать массив Zi и найти его максимальный (max) и минимальный (min) элемент и их индексы (n и k соответственно).

для ; .

Для подсчета количества элементов в массиве Z следует воспользоваться формулой:

, где xn=-2; xk= 6; Δx= 0,4; ]a[ - выделение целой части числа a.

Блок - схема решения этой задачи приведена на рис. 10.

В блоке 3 задается значение константы P, определяется число повторений цикла (m), оно означает и количество элементов массива Z, задается начальное значение x. Блок 4 организует цикл по переменной i, которая является индексом элементов массива Z. Блоки 5 и 6 обеспечивают формирование массива Z и вывод его элементов, а в блоке 7 организовано изменение величины x для следующего прохождения цикла. В блоке 8 присваивается значение первого элемента массива Z переменным b и c, а также запоминается индекс первого элемента (для случая, если он окажется наибольшим или наименьшим среди всех других элементов). Блок 9 организует цикл по переменной i, начиная с i=2.

В блоках 10 и 11 происходит выбор наибольшего значения из элементов массива Z и запоминание его индекса, а в блоках 12, 13 запоминаются наименьшее значение и индекс соответствующего элемента. Блок 14 выводит результаты: наибольшее и наименьшее значения и их индексы.

Рисунок 10 - Блок-схема алгоритма определения максимального и минимального значения

8. Алгоритмы сортировки

Сортировка применяется во всех без исключения областях программирования: в математических вычислениях, инженерных расчетах, при обработке данных и др.

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

8.1. Сортировка обменом (пузырьковая сортировка)

Этот метод называется также пузырьковой сортировкой. Идея этого метода отражена в его названии. Самые "легкие" элементы массива "всплывают" наверх подобно пузырькам. Алгоритм метода следующий. Слева направо поочередно сравниваются два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих элемента и так далее до конца массива. После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Всего требуется n-1 проход, где n – длина массива.

Блок-схема алгоритма сортировки массива А по возрастанию значений его элементов методом обмена (пузырька) приведена на рис. 11.

Рисунок 11 - Блок-схема алгоритма сортировки массива А методом пузырька