- •7. Одномерные массивы 114
- •8. Обработка двумерных массивов (матриц) 162
- •9. Обработка строк 183
- •10. Тип данных, определенный пользователем. Структуры 214
- •11. Использование подпрограмм 228
- •Приложение 52 310 Список литературы 313 Введение
- •1. Этапы создания Windows-приложения
- •2. Среда Visual Basic 2005
- •2.1. Структура среды Visual Basic 2005
- •2.2. Создание нового проекта
- •2.3. Сохранение проекта
- •2.4. Выполнение приложения
- •2.5. Основные команды среды Visual Basic 2005
- •2.6. Методы тестирования
- •2.7. Отладка приложений в среде vb
- •3. Разработка интерфейса в среде vb. Основные элементы управления
- •3.1. Метка
- •3.2. Текстовое поле
- •3.3. Кнопка
- •3.4. Окно списка
- •3.5. Выравнивание положения элементов управления
- •4. Программа линейной структуры
- •4.1. Понятие переменной
- •4.2. Типы данных
- •4.3. Объявление переменных
- •4.4. Оператор присваивания
- •Оператор присваивания работает справа налево.
- •4.5. Константы
- •4.6. Арифметические операции
- •4.7. Математические функции
- •4.8. Арифметическое выражение
- •4.9. Окно ввода (InputBox)
- •4.10. Окно вывода сообщения (MsgBox)
- •4.11. Пример. Вычисление площади треугольника
- •4.12. Пример. Нахождение цифр числа
- •5. Организация ветвлений
- •5.1. Логические константы и переменные
- •5.2. Операции сравнения
- •5.3. Логические операции
- •5.4. Логическое выражение
- •5.5. Условный оператор
- •5.6. Функция iIf
- •5.7. Оператор множественного ветвления ElseIf
- •5.8. Оператор выбора Select Case
- •5.9. Оператор безусловного перехода GoTo
- •5.10. Пример. Решение линейного уравнения
- •5.11. Пример. Программа-калькулятор
- •6. Программирование повторений
- •6.1. Цикл со счетчиком
- •6.1.1. Табуляция функции
- •6.1.2. Вычисление факториала
- •6.1.3. Обработка совокупности чисел с известным числом элементов
- •6.2. Цикл с условием
- •6.2.1. Ввод с проверкой
- •6.2.2. Обработка совокупности чисел с неизвестным числом элементов
- •6.2.3. Вычисление суммы ряда по общей формуле
- •Вычисление суммы ряда с использованием рекуррентного соотношения
- •6.2.5. Вычисление произведения ряда
- •Решение нелинейных уравнений методом простой итерации
- •7. Одномерные массивы
- •Массивы всегда обрабатываются в цикле.
- •7.1. Ввод массива
- •Вывод массива в окно списка и в текстовое поле
- •7.3. Вычисление суммы и произведения элементов массива
- •7.4. Определение количества элементов массива, удовлетворяющих некоторому условию
- •7.5. Вычисление среднего арифметического и среднего геометрического элементов массива, удовлетворяющих некоторому условию
- •7.6. Нахождение максимального элемента массива
- •7.7. Нахождение минимального элемента массива, удовлетворяющего некоторому условию
- •7.8. Поиск первого элемента массива, удовлетворяющего некоторому условию
- •7.9. Поиск последнего элемента массива, удовлетворяющего некоторому условию
- •7.10. Замена одного элемента массива
- •7.11. Замена всех элементов массива, удовлетворяющих некоторому условию
- •7.12. Перестановка местами двух элементов массива
- •7.13. Формирование нового массива из некоторых элементов исходного массива
- •7.14. Проверка совпадения всех элементов массива
- •7.15. Проверка упорядоченности всех элементов массива
- •7.16. Сортировка массива методом пузырька
- •7.17. Линейная сортировка массива (методом поиска минимума)
- •Никогда нельзя использовать одновременно оба способа перестановки элементов массива.
- •8. Обработка двумерных массивов (матриц)
- •8.1. Ввод прямоугольной матрицы
- •8.2. Вывод прямоугольной матрицы в окно списка и в текстовое поле
- •8.3. Поиск максимального элемента матрицы
- •8.4. Обработка матрицы по строкам
- •8.5. Обработка матрицы по столбцам
- •8.6. Обработка квадратных матриц
- •Для обработки элементов, стоящих на любой диагонали, достаточно одного цикла. Для обработки элементов, принадлежащих к одному из треугольников, необходимо использовать вложенные циклы.
- •9. Обработка строк
- •9.1. Основные функции обработки строк
- •9.2. Посимвольная обработка строки
- •9.3. Формирование массива слов строки
- •9.4. Формирование строки из массива слов
- •9.5. Слова-палиндромы
- •9.6. Выделение чисел из строки
- •9.7. Сравнение строк
- •9.8. Обработка многострочного текста
- •10. Тип данных, определенный пользователем. Структуры
- •10.1. Описание структуры. Область видимости. Понятие метода
- •10.2. Оператор With
- •10.3. Ввод массива структур
- •10.4. Вывод массива структур
- •10.5. Поиск в массиве структур
- •10.6. Формирование нового массива из некоторых элементов исходного массива
- •10.7. Сортировка массива структур
- •11. Использование подпрограмм
- •11.1. Определение процедуры и функции. Описание процедуры и функции
- •11.2. Передача параметров по ссылке и по значению
- •11.3. Формальные параметры и фактические переменные
- •11.4. Локальные и глобальные переменные
- •11.5. Static-переменные
- •Приложение 1
- •Приложение 2
- •Приложение 3
- •Приложение 4
- •Приложение 5
- •Приложение 6
- •Приложение 7
- •Приложение 8
- •Приложение 9
- •Приложение 10
- •Приложение 11
- •Приложение 12
- •Приложение 13
- •Приложение 14
- •Приложение 15
- •Приложение 16
- •Приложение 17
- •Приложение 18
- •Приложение 19
- •Приложение 20
- •Приложение 21
- •Приложение 22
- •Приложение 23
- •Приложение 24
- •Приложение 25
- •Приложение 26
- •Приложение 27
- •Приложение 28
- •Приложение 29
- •Приложение 30
- •Приложение 31
- •Приложение 32
- •Приложение 33
- •Приложение 34
- •Приложение 35
- •Приложение 36
- •Приложение 37
- •Приложение 38
- •Приложение 39
- •Приложение 40
- •Приложение 41
- •Приложение 42
- •Приложение 43
- •Приложение 44
- •Приложение 45
- •Приложение 46
- •Приложение 47
- •Приложение 48
- •Приложение 49
- •Приложение 50
- •Приложение 51
- •Приложение 52
- •Список литературы
7.16. Сортировка массива методом пузырька
Отсортировать массив – значит, переставить его элементы таким образом, чтобы для каждой пары выполнялось заданное условие упорядоченности (см. раздел 7.15). Существует множество различных способов сортировки массива. Мы рассмотрим два самый простых: метод пузырька (или метод наивной сортировки) и метод линейной сортировки (см. раздел 7.17).
Метод пузырька предлагает сравнивать каждый элемент с соседним. Если два элемента стоят неправильно, нарушая условие сортировки, то их меняют местами. Процесс перестановки продолжается до тех пор, пока все элементы не окажутся на своих местах. Тогда для всех пар элементов массива будет выполняться условие упорядоченности, и массив будет отсортирован. В таблице 9 приведен пример сортировки массива по возрастанию методом пузырька.
Таблица 9
Массив |
Действие |
1 3 5 2 4 |
Сравниваем первую пару элементов. Числа 1 и 3 стоят в правильном порядке. Их переставлять не надо. Делаем один шаг по массиву и сравниваем числа 3 и 5. Их тоже не надо переставлять. Делаем еще один шаг и сравниваем числа 5 и 2. Они стоят в неправильном порядке, поэтому мы их меняем местами. |
1 3 2 5 4 |
Сдвигаемся еще на один элемент и сравниваем числа 5 и 4. Они тоже стоят неправильно, и мы меняем их местами. |
1 3 2 4 5 |
Мы дошли до конца массива. Но массив пока неупорядочен. Поэтому мы возвращаемся к началу массива и продолжаем сравнение. Числа 1 и 3 идут в правильном порядке, а вот числа 3 и 2 порядок нарушают, поэтому мы меняем их местами. |
1 2 3 4 5 |
Пройдя еще один раз по всему массиву, мы убеждаемся, что все элементы стоят на своих местах. Значит, процесс сортировки массива можно завершить. |
Рассмотрим особенности программной реализации данного алгоритма на примере задачи сортировки по возрастанию элементов целочисленного массива.
Для решения задачи объявим вспомогательные переменные. Логическая переменная 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. Пример работы программы сортировки массива методом пузырька