КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сортировка. Здесь вы не узнаете ничего нового о Visual Basic
Здесь вы не узнаете ничего нового о Visual Basic. Будем совершенствовать технику программирования.
Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочивание по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и строки (как слова в словаре). Сортировка - очень распространенная вещь в самых разных программах, в частности - в системах управления базами данных.
Задача: Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию. Идея решения: Если мы не можем сходу запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел? Мы бы запаслись пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место, а на его место в исходном массиве - 0. И так далее. Вот программа для 10 чисел: Const N = 10 'N - размер массива Dim massiv_ishodn(1 To N) As Integer 'Это исходный массив Dim massiv_rezult(1 To N) As Integer 'Это наш пустой лист бумаги
'Вспомогательная функция для поиска максимума в массиве m(1 To N). Она выдает значение 'максимального элемента (maximum) и заодно номер этого элемента (Nomer_max): Private Function maximum(m, N As Integer, Nomer_max As Integer) As Integer Dim i As Integer, max As Integer max = m(1): Nomer_max = 1 'max - "временный" максимум For i = 2 To N If max < m(i) Then max = m(i) Nomer_max = i End If maximum = max Next End Function
'Основная процедура сортировки исходного вектора mass_ish размера N в результирующий - mass_rez:
Private Sub sortirovka(mass_ish, N As Integer, mass_rez) Dim Nom_max As Integer For i = 1 To N mass_rez(N + 1 - i) = maximum(mass_ish, N, Nom_max) 'Пишем "в правую клетку" mass_ish(Nom_max) = 0 'Ноль - на старое место Next End Sub
Private Sub Command1_Click() massiv_ishodn(1) = 41 'Задаем значения элементов исходного массива massiv_ishodn(2) = 8 massiv_ishodn(3) = 17 massiv_ishodn(4) = 82 massiv_ishodn(5) = 20 massiv_ishodn(6) = 2 massiv_ishodn(7) = 30 massiv_ishodn(8) = 12 massiv_ishodn(9) = 6 massiv_ishodn(10) = 9
sortirovka massiv_ishodn, N, massiv_rezult 'Сортируем массив
For i = 1 To N Debug.Print massiv_rezult(i); 'Распечатываем отсортированный массив Next End Sub
Функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще порядковый номер максимального элемента - Nomer_max. Это называется побочным эффектом функции.
Методов сортировки много. Приведенный метод - самый примитивный. Мало того, что нам пришлось расходовать память на второй массив, для выполнения сортировки массива из 100 элементов понадобилось бы около 100*100=10000 операций сравнения элементов массива между собой. Существуют методы гораздо более эффективные. Приведу один из них - метод пузырька. Представьте себе тонкую вертикальную трубку с водой. Запустим снизу пузырек воздуха. Он поднимется до самого верха и остановится. Затем пустим еще один. Он поднимется наверх и остановится сразу же под первым. Затем запустим третий и так далее все сто пузырьков. А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы. Вот алгоритм: Сравним первый элемент массива со вторым, и если второй больше, то ничего не делаем, а если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами - если третий больше, то ничего не делаем, а если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и так далее. Где-то по пути мы встретим максимальный элемент, и он, как пузырек, поднимется у нас до самого верха.
Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из остальных 99 элементов. Метод тот же. Запускаем второй пузырек и так далее. Метод пузырька не требует второго массива, да и сравнений здесь в два раза меньше. Вот программа: Const N = 10 'N - размер массива Dim massiv(1 To N) As Integer 'Это массив
'Сортировка массива mass размером Razmer: Private Sub puziryok(mass, Razmer As Integer) Dim i As Integer For m = Razmer To 2 Step -1 'Всего пузырьков - 9 For i = 1 To m - 1 'i увеличивается - пузырек ползет вверх If mass(i) > mass(i + 1) Then 'Стоит ли обмениваться значениями c = mass(i) 'Три оператора для обмена значений двух элементов с помощью mass(i) = mass(i + 1) 'транзитного элемента c mass(i + 1) = c End If Next i Next m End Sub
Private Sub Command1_Click() massiv(1) = 41 'Задаем значения элементов массива massiv(2) = 8 massiv(3) = 17 massiv(4) = 82 massiv(5) = 20 massiv(6) = 2 massiv(7) = 30 massiv(8) = 12 massiv(9) = 6 massiv(10) = 9
puziryok massiv, N 'Сортируем массив
For i = 1 To N Debug.Print massiv(i); 'Распечатываем отсортированный массив Next End Sub В заключение скажу, что существуют методы гораздо более эффективные, чем метод пузырька. Задание 132: Отсортируйте по возрастанию двумерный массив. Я имею в виду - нужно сделать так, чтобы: а(1,1) <= a(1,2) <=... <= a(1,N) <= <= a(2,1) <= a(2,2) <=... <= a(2,N) <= <= a(3,1) <= a(3,2) <=...
Дата добавления: 2014-12-23; Просмотров: 698; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |