Метод пузырька
Методов сортировки много. Приведенный метод – самый примитивный. Мало того, что нам пришлось расходовать память на второй массив, нам для выполнения сортировки массива из 100 элементов понадобилось бы около 100*100=10000 операций сравнения элементов массива между собой.
Существуют методы гораздо более эффективные. Приведу один из них – метод пузырька. Представьте себе тонкую вертикальную трубку с водой. Запустим снизу пузырек воздуха. Он поднимется до самого верха и остановится. Затем пустим еще один. Он поднимется наверх и остановится сразу же под первым. Затем запустим третий и так далее все сто пузырьков.
А теперь представим, что это не трубка, а наш исходный массив, а вместо пузырьков поднимаются максимальные элементы, сначала самый максимальный, потом - следующий по величине и т.д.
Вот алгоритм: Сравним первый элемент массива со вторым, и если второй больше, то это хорошо, так как они расположены в порядке возрастания. Мы ничего не делаем. А вот если первый больше, то меняем местами первый и второй элементы. В этом вся соль метода. Затем повторяем это со вторым и третьим элементами – если третий больше, то ничего не делаем, а если второй больше, то меняем местами второй и третий элементы. Затем повторяем все это с третьим и четвертым элементами и так далее. Где-то по пути мы встретим максимальный элемент, и он, согласно нашей механике постоянно меняясь местами с вышестоящими соседями, как пузырек, поднимется у нас до самого верха.
Теперь, когда мы знаем, что элемент номер 100 у нас самый большой, нам предстоит решить задачу сортировки для массива из остальных 99 элементов. Метод тот же. Запускаем второй пузырек и так далее.
Метод пузырька не требует второго массива, да и сравнений здесь в два раза меньше.
Вот программа:
'Сортировка массива mass размером N+1:
Sub puziryok(ByVal mass() As Integer, ByVal N As Integer)
Dim i, c, m As Integer
For m = N To 1 Step -1 'Всего пузырьков - 9
For i = 0 To m - 1 'i увеличивается - пузырек ползет вверх
If mass(i) > mass(i + 1) Then 'Стоит ли обмениваться значениями
c = mass(i) 'Три оператора для обмена значений
mass(i) = mass(i + 1) 'двух элементов с помощью
mass(i + 1) = c 'транзитного элемента c
End If
Next i
Next m
End Sub
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim massiv() As Integer = {41, 8, 17, 82, 20, 2, 30, 12, 6, 9} 'Это массив
Dim N As Integer = massiv.Length - 1 'Это его размер без 1
puziryok(massiv, N) 'Сортируем массив
Dim i As Integer
For i = 0 To N
Debug.WriteLine(massiv(i)) 'Распечатываем отсортированный массив
Next
End Sub
В заключение скажу, что существуют методы гораздо более эффективные, чем даже метод пузырька.
Задание 108.
Задача для ученого-диетолога: Определить связь между ростом и весом боксеров-профессионалов. Для этого диетолог измерил рост и вес нескольких сотен боксеров и записал результаты измерений в длинную таблицу:
|
Фамилия |
Рост |
Вес |
|
Иванов |
173 |
71 |
|
Петров |
182 |
93 |
|
Сидоров |
169 |
62 |
|
Николаев |
175 |
70 |
|
……………. |
………………. |
…………….. |
Для более наглядного представления о характере связи между ростом и весом необходимо упорядочить эту таблицу по весу:
|
Фамилия |
Рост |
Вес |
|
Сидоров |
169 |
62 |
|
Николаев |
175 |
70 |
|
Иванов |
173 |
71 |
|
Петров |
182 |
93 |
Для проведения упорядочивания приглашается программист, то есть вы. Считайте, что вам заданы три исходных массива.
