Нахождение наибольшего и наименьшего значений в числовом массиве.

Дан числовой массив М (i), i = 1, 2, …, N. Необходимо определить номер элемента с наибольшим значением.

Начало

Ввод N, M

Nmax : = 1

Mmax : = M(1)

i := 2, …, N

да

M(i) > Mmax Mmax : = M(i)

Nmax : = i

нет

Вывод Nmax,

Mmax

Конец

Рис.3. Блок-схема алгоритма нахождения

наибольшего элемента массива М

Здесь используются две вспомогательные переменные Mmax и Nmax.Первая предназначена для запоминания значения элемента, вторая – для его порядкового номера. Перед началом цикла этим переменным присваиваются начальные значения – параметры первого элемента массива. На каждом шаге цикла текущий элемент сравнивается с Mmax и если он оказывается больше, Mmax получает новое значение, одновременно запоминается номер этого элемента.

По окончании цикла переменные Mmax и Nmax будут равны соответственно максимальному значению в массиве M и порядковому номеру максимального элемента.

Примечание. Для того, чтобы отыскать наименьший элемент в заданном массиве достаточно в приведенном алгоритме заменить имена переменных Mmax и Nmax на Mmin и Nmin и в цикле проверять выполнение условия вместо условия M(i) < Mmin.

Кроме того, за один проход можно получить обе величины: и Mmax и Mmin. Для этого на каждом шаге цикла нужно проверять два условия – M(i) < Mmin и M(i) > Mmax. Bи при необходимости изменять значения либо Mmin, либо Mmax.

Сортировка числового массива.

Пусть задан числовой массив М, содержащий N элементов, и необходимо его упорядочить его по возрастанию, то есть перенумеровать элементы этого массива так, чтобы выполнялось условие М ₁ £ М ₂ £ … £ М _N.

Существует несколько вариантов алгоритма сортировки. Один из них получил название «метод пузырька» и заключается в следующем.

Вводится понятие инверсии, которое означает ситуацию, когда имеет место нарушение порядка расположения элементов в заданном массиве. Например, если массив должен быть упорядочен по возрастанию, а два каких-либо соседних элемента этому свойству не удовлетворяют, то есть имеет место отношение М_i > М _i+1. Тогда говорят, что имеет место инверсия элементов с номерами i и i +1.

Суть метода пузырька состоит в том, что в заданном массиве по очереди сравниваются соседние элементы между собой и в случае появления инверсии ее устраняют – у таких элементов изменяют значения, М _{i +1} получает значение М _i, а М_{i +1}. – значение М _i. Это процедуру (проверку массива) повторяют несколько раз, до тех пор, пока все инверсии не будут устранены. Отсутствие инверсий означает упорядоченность массива.

На рис. 4 показана блок схема одного из вариантов алгоритма сортировки методом пузырька.

Сортировка

1

Ввод N, M

да F : = 1

F : = 0 нет

i := 1,2, …, N-1Вывод M

нет

M _{i +1} < M _i

да Конец

C := M _{i +1}

M _{i +1}:= M _i

M _i := C

F:=1

1

Рис.4. Блок-схема алгоритма сортировки

В приведенной схеме используются две вспомогательные переменные – F и C. Перед началом цикла переменной F присваивается значение 0. Это признак упорядоченности массива. Если изначально массив M уже упорядочен, то в процессе цикла перебора его элементов условие М_i > М _i+1 ни разу не будет выполнено и значение F останется равным 0. Это признак того, что массив уже упорядочен. Если же в процессе перебора хотя бы одна инверсия встретится, значение F изменится на 1 и в этом случае процесс нужно повторить.

Переменная C нужна для осуществления обмена значениями между элементами М_i и М _i+1 в случае, если имеет место инверсия.