Поиск наибольших или наименьших элементов в массивах

 

Алгоритм поиска экстремальных значений в массиве состоит в следую­щем. Например, требуется определить максимальный элемент массива X. При­нимаем первоначально за наибольший первый элемент массива X, присваивая его значение переменной , т. е. . Затем сравниваем с этой переменной каждый очередной элемент, начиная со 2-го. Если очередной элемент меньше, , переходим к проверке следующего элемента. Если же , присваиваем переменной  значение i -того элемента массива X, т. е.  и продолжаем сравнивать следующие элементы массива X уже с этим новым значением . Если встретится число еще большее, снова произ­водим присваивание и т. д. Последнее значение  после окончания просмотра всех элементов массива X и будет наибольшим.

Пример. В векторе  определить наибольший элемент и его номер.

 

Sub Massiv10()

Dim Y(l To 40) As Single

Dim Max As Single 'Максимальный элемент

Dim i As Integer

Dim k As Integer 'Номер max элемента

 

'Ввод массива

'---------------------

 

'Поиск максимального элемента

Мах = Y(l) 'Начальное значение максимума

к = 1 'Начальное значение номера max элемента

For i = 2 To 40

If Y(i) > Max Then

Max = Y(i) 'Новое значение максимума k = i

'Новый номер max элемента

End If

Next i

End Sub

 

Если требуется определить наименьший элемент массива, то в условии If знак > нужно заменить на знак <.

 

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

 

Сортировкой массива (или ранжирование) называется расположение элементов массива в порядке возрастания или убывания их значений (размещение элементов по рангу). Об­щий метод решения задачи ранжирования состоит в просмотре массива, срав­нении друг с другом каждой пары рядом стоящих элементов и перемене их местами, если они стоят «не по рангу».

Для решения задачи ранжирования можно использовать метод «пузырька». Суть метода состоит в следующем. Например, необходимо упорядочить массив X по возрастанию. Согласно методу «пузырька», последовательно просматривается массив, сравнивая каждый i -й его элемент со следующим - м и проверяя их на условие . При этом все пары соседних элементов, удовлетворяющие этому условию, т.е. стоящие «по рангу», пропускаются, а пары, не удовлетво­ряющие ему, т.е. стоящие не «по рангу», переставляются местами. В заранее заданной переменной, например Flag, запоминается, были ли перестановки за весь цикл просмотра.

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

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

Сравнение пар чисел  и  следует вести при изменении индекса от  до , где  – переменное количество просматриваемых элементов. Последнее из этих значений i будет соответствовать сравнению предпоследнего элемента массива с последними, ибо последний элемент сравнивать уже не с чем.

Для программной реализации перестановки двух элементов используется следующий алгоритм обмена значений двух переменных А и В: значение пере­менной А запоминается во вспомогательной переменной С, затем переменной А присваивается значение переменной В, а переменной В - значение перемен­ной С.

Пример. Ранжировать в порядке возрастания вектор .

 

Sub Massiv11()

Rem Сортировка массива по возрастанию

Dim A(1 To 20) As Single

Dim С As Single 'Вспомогательная переменная

Dim Flag As Boolean 'Флаг перестановок

Dim i As Integer, n As Integer

 

'Ввод массива

 

'Включить генератор случайных чисел

Randomize

For i = 1 To 20

A(i) = Rnd

'MsgBox A(i)

Next i

 

 

'Ранжирование массива

n = 20 'Количество элементов в массиве

Do

Flag = False 'Перестановок не было

n = n - 1 'Индекс последнего элемента при сравнении

'Цикл просмотра

For i = 1 To n

'Проверка расположения элементов по рангу

If A(i) > A(i + 1) Then

   'Перестановка

   С = A(i)

   A(i) = A(i + 1)

   A(i + 1) = С

   Flag = True 'Произошла перестановка

End If

Next i

Loop While Flag 'Перейти к началу цикла,

'если были перестановки

 

'Вывод отсортированного массива

For j = 1 To 20

str_msg = str_msg & Chr(13) & A(j) & ", "

Next

 'вызываем стандартное диалоговое окно с кнопкой OK и помещаем надпись

MsgBox "Введено: " & str_msg,, "Вывод ранее введенного массива"

End Sub

 

Для ранжирования массива по убыванию в приведенном фрагменте про­граммы достаточно в операторе If знак > поменять на знак <.

Кроме сортировки методом «пузырька» существует другие методы сортировки массивов, отличающиеся скоростью работы алгоритма.