Введение 8 Этапы создания Windowsприложения 8
 Скачать 6.98 Mb.
|
7.16. Сортировка массива методом пузырькаОтсортировать массив – значит, переставить его элементы таким образом, чтобы для каждой пары выполнялось заданное условие упорядоченности (см. раздел 7.15). Существует множество различных способов сортировки массива. Мы рассмотрим два самый простых: метод пузырька (или метод наивной сортировки) и метод линейной сортировки (см. раздел 7.17). Метод пузырька предлагает сравнивать каждый элемент с соседним. Если два элемента стоят неправильно, нарушая условие сортировки, то их меняют местами. Процесс перестановки продолжается до тех пор, пока все элементы не окажутся на своих местах. Тогда для всех пар элементов массива будет выполняться условие упорядоченности, и массив будет отсортирован. В таблице 9 приведен пример сортировки массива по возрастанию методом пузырька. Таблица 9
Рассмотрим особенности программной реализации данного алгоритма на примере задачи сортировки по возрастанию элементов целочисленного массива. Для решения задачи объявим вспомогательные переменные. Логическая переменная sort предназначена для хранения информации о состоянии массива. Она показывает, отсортированы элементы массива или нет. Dim sort As Boolean Так как сортировка массива связана с перестановкой его элементов, то нам потребуется переменная для временного хранения одного из переставляемых элементов (см. раздел 7.12). Очевидно, что тип этой переменной всегда будет совпадать с типом элементов массива. Dim z As Integer Нам потребуется несколько раз проходить по массиву, ища пары элементов, стоящих в неправильном порядке. Для этого организуем цикл. Число повторов заранее неизвестно, следовательно, надо использовать цикл с условием. Нам придется обязательно пройти по массиву хотя бы один раз, чтобы удостовериться, что все элементы стоят на своих местах. Поэтому применим цикл с постусловием. Его выполнение завершится, когда массив будет полностью отсортирован. Do Перед началом каждого нового прохода по массиву предполагаем, что он отсортирован. В переменную sort записываем значение Истина (True). sort = True Организуем цикл для проверки всех элементов массива, от нулевого до предпоследнего. Так как на каждом шаге цикла мы будем сравнивать элементы с номерами i и (i+1), то завершить цикл надо, когда значение счетчика i станет равным n-1. В этом случае на последнем шаге цикла будут сравниваться элементы с номерами (n-1) и n. Если цикл после этого шага не прервать, то программа станет сравнивать элементы с номерами n и (n+1). Элемент с номером (n+1) в массиве отсутствует, поэтому произойдет аварийное завершении программы и ответ получен не будет. For i = 0 To n – 1 Анализируем соседние элементы. If a(i) > a(i + 1) Then Если элемент a(i) больше элемента a(i + 1), то есть предшествующий элемент больше, чем последующий, значит, элементы стоят неправильном порядке и их необходимо поменять местами. Для этого используем дополнительную переменную z. Процесс перестановки элементов описан в разделе 7.12. z = a(i) a(i) = a(i + 1) a(i + 1) = z Так как элементы стояли в неправильном порядке, значит, массив не был отсортирован, поэтому в логическую переменную sort записываем значение Ложь (False). sort = False End If Next Loop Until sort После завершения всех циклов мы можем вывести отсортированный массив. Сначала выводим горизонтальную черту, чтобы зрительно отделить исходные данные от результатов. lstA.Items.Add("-------------------------------") Печатаем поясняющий заголовок. lstA.Items.Add("Массив после сортировки") Затем последовательно в цикле выводим все элементы отсортированного массива. Использование константы vbTab позволяет организовать вывод в две колонки. For i = 0 To n lstA.Items.Add(Str(i) + vbTab + Str(a(i))) Next Полный текст программы представлен в приложении 35. Пример работы программы приведен на рис. 50.  Рис. 50. Пример работы программы сортировки массива методом пузырька |