Главная Обратная связь

Дисциплины:






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



 

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

Для решения задачи ранжирования можно использовать метод «пузырька». Суть метода состоит в следующем. Например, необходимо упорядочить массив 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 знак > поменять на знак <.

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

 





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...