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

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

Пример. Сформировать массив 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.1. Сортировка обменом (пузырьковая сортировка)

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

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

  

 

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

 

Сортировка выбором

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

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

 

           

 

Рисунок 12 - Блок-схема алгоритма сортировки массива А методом выбора

 

Метод перестановок

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

Блок-схема алгоритма сортировки массива А методом перестановок приведена на рис. 13.

          

 

Рисунок 13 - Алгоритм сортировки массива А методом перестановок

Сортировка вставкой

Массив разделяется на две части: на отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. Первоначально, в качестве отсортированной части массива, принимают только один первый элемент, а в качестве не отсортированной части - все остальные элементы.

Таким образом, алгоритм будет состоять из n -1 прохода (где n – длина массива), каждый из которого, будет включать четыре действия:

1. Взятие очередного, начиная со второго, i -го не отсортированного элемента и сохранение его в дополнительной переменной B;

2. Сравнение переменной B с j -ми элементами отсортированной части массива и поиск позиции j _ vst, в которой вставка взятого элемента не нарушит упорядоченности элементов этой части массива;

3. Сдвиг элементов массива вправо от j _ vst -го до i -го элемента, для того чтобы освободить найденную позицию вставки;

4. Вставка взятого элемента в найденную j _ vst позицию.

Блок-схема алгоритма сортировки массива А методом вставок приведена на рис. 14.

 

Рисунок 14 - Блок-схема алгоритма сортировки массива А методом вставок