Введение 8 Этапы создания Windowsприложения 8
 Скачать 6.98 Mb.
|
7.17. Линейная сортировка массива (методом поиска минимума)Сортировка массива методом поиска минимума является одним из частных случаев линейной сортировки. Она может использоваться как для сортировки по возрастанию, так и по убыванию. При сортировке по возрастанию метод предлагает найти минимальный элемент в массиве и поставить его на нулевое место. А элемент с нулевого места переместить на место минимального элемента. После этого нулевой элемент массива гарантировано стоит на своем месте. Поэтому в дальнейшей сортировке он не участвует. На следующем шаге массив просматривается уже с первого элемента. В этой части находится свой минимум, которой меняется местами с первым элементом. Теперь уже два элемента массива стоят на своих местах. На следующем шаге массив обрабатывается со второго элемента. Процесс продолжается до тех пор, пока в необработанной части массива не останутся два элемента. Среди них тоже находится минимальный. Он ставится на предпоследнее место массива. А последний необработанный элемент автоматически попадает на последнее место в массиве. Теперь все элементы стоят на своих местах и процесс сортировки можно прекратить. В таблице 10 приведен пример сортировки массива по возрастанию методом поиска минимума. Таблица 10
Сортировка методом поиска минимума является одним из частных случаев линейной сортировки. Остальные варианты приведены в таблице 11. Таблица 11
Помимо этих вариантов существует еще один частный случай линейной сортировки. Это минимаксная сортировка (иногда встречается другое ее название – максиминная). Согласно данному методу в необработанной части массива одновременно ищется максимальный и минимальный элементы, которые затем расставляются по своим местам в зависимости от направления сортировки. При этом необработанная часть массива сокращается одновременно с двух сторон. Рассмотрим особенности программной реализации алгоритма сортировки целочисленного массива по возрастанию методом поиска минимума. Для решения задачи нам потребуется несколько дополнительных переменных. Переменная start предназначена для хранения номера элемента, с которого начинается необработанная часть массива. Dim start As Integer На каждом шаге основного цикла мы будем искать минимальный элемент в необработанной части массива. При этом нам потребуются переменные для хранения значения минимального элемента (min) и его номера (imin). Переменная min всегда будет иметь такой же тип, что и элементы массива. Переменная imin всегда будет иметь целочисленный тип данных. Dim imin, min As Integer Организуем основной цикл. На первом шаге алгоритма линейной сортировки начало необработанной части массива совпадает с началом самого массива, то есть с нулевым элементом. После каждого шага цикла начало необработанной части будет смещаться на один элемент к концу массива. На последнем аге цикла в необработанной части массива остается всего два элемента. Очевидно, что при этом начало необработанной части массива будет совпадать с предпоследним элементом массива, то есть с элементом, имеющим номер (n-1) For start = 0 To n – 1 На каждом шаге цикла мы будем искать минимальный элемент в необработанной части массива. Поиск удобно начинать с первого элемента необработанной части. Его номер всегда совпадает со значением, записанным в переменной start. Запоминаем стартовый элемент необработанной части как минимум. min = a(start) В специальную переменную записываем соответствующий номер элемента. imin = start Организуем цикл для поиска минимального элемента в необработанной части массива. Цикл начнется с элемента, следующего за стартовым, и будет идти до конца необработанной части. В нашей задаче конец необработанной части совпадает с концом массива. For i = start + 1 To n Анализируем очередной элемент массива. If a(i) < min Then Если этот элемент меньше ранее найденного минимума, то значение минимума надо обновить, записав в него значение проверяемого элемента массива. min = a(i) В другую переменную записываем номер найденного минимального элемента. Этот номер мы будем использовать при перестановке элементов массива. imin = i End If Next После завершения цикла поиска минимума, мы должны поменять местами найденное минимальное значение и стартовый элемент необработанной части массива. Это можно сделать двумя различными способами. Первый способ – традиционный, рассмотренный в разделе 7.12. Он предлагает использовать дополнительную переменную, в которую временно записывается значение одного из переставляемых элементов. Программный код при этом выглядит следующим образом. Dim z As Integer z = a(start) a(start) = a(imin) a(imin) = z Второй способ применяется только при решении задачи линейной сортировки и не может быть распространен на другие случаи. На место минимального элемента из необработанной части записывается значение стартового элемента необработанной части. a(imin) = a(start) Затем на место стартового элемента записывается значение минимального элемента, которое хранится в переменой min. a(start) = min Никогда нельзя использовать одновременно оба способа перестановки элементов массива. Next После завершения основного цикла выводим отсортированный массив. Сначала печатаем горизонтальную черту, чтобы зрительно отделить исходные данные от результатов. lstA.Items.Add("-------------------------------") Потом выводим поясняющий заголовок. lstA.Items.Add("Массив после сортировки") И последовательно в цикле печатаем все элементы отсортированного массива. Использование константы vbTab позволяет организовать вывод в две колонки. For i = 0 To n lstA.Items.Add(Str(i) + vbTab + Str(a(i))) Next Полный текст программы представлен в приложении 36. Пример работы программы приведен на рис. 51.  Рис. 51. Пример работы программы линейной сортировки массива | |||||||||||||||||||||||