10. Сортировка

Здесь вы не узнаете ничего нового о собственно языке VB. Будем совершенствовать универсальную технику программирования.

Пусть имеется ряд чисел: 8 2 5 4. Под сортировкой понимают их упорядочивание по возрастанию (2 4 5 8) или убыванию (8 5 4 2). Сортировать можно и строки (как слова в словаре).

Сортировка – очень распространенная вещь в самых разных программах, в частности – в системах управления базами данных. Несмотря на то, что класс Array имеет специальный метод для сортировки массива, этого явно недостаточно. Вы должны уметь сортировать сами.

1. Простая сортировка

Задача: Задан массив из 100 произвольных положительных чисел. Отсортировать его по возрастанию.

Идея решения: Отсутствует. Тогда поговорим об идее поиска идеи. Если мы не можем придумать, как запрограммировать задачу, нужно подробно представить себе, в каком порядке мы решали бы ее вручную, без компьютера. Как бы мы сами сортировали 100 чисел, записанных на бумаге? Мы сделали бы вот что. Запаслись карандашом, ластиком и другим, пустым листом бумаги из 100 клеток. Затем нашли бы в исходном массиве максимальное число и записали его в самую правую клетку, а в исходном массиве на его месте записали бы число, меньшее самого маленького в массиве (в нашем случае подойдет 0). Затем нашли бы в изменившемся исходном массиве новое максимальное число и записали его на второе справа место, а на его место в исходном массиве – 0. И так далее.

Вот программа, воплощающая эту идею для 10 чисел:

'Вспомогательная функция для поиска максимума в массиве m размера N+1. Она выдает значение

'максимального элемента (maximum) и заодно мы узнаем номер этого элемента (Nomer_max):

Function maximum(ByVal m() As Integer, ByVal N As Integer, ByRef Nomer_max As Integer) As Integer

Dim i, max As Integer

max = m(0) : Nomer_max = 0 'max - "временный" максимум

For i = 1 To N

If max < m(i) Then

max = m(i)

Nomer_max = i

End If

maximum = max

Next

End Function

'Основная процедура сортировки исходного массива mass_ish размера N+1 в результирующий - mass_rez:

Sub sortirovka(ByVal mass_ish() As Integer, ByVal N As Integer, ByVal mass_rez() As Integer)

Dim i, Nom_max As Integer

For i = 0 To N

mass_rez(N - i) = maximum(mass_ish, N, Nom_max) 'Пишем "в правую клетку"

mass_ish(Nom_max) = 0 'Ноль - на старое место

Next

End Sub

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click

Dim massiv_ishodn() As Integer = {41, 8, 17, 82, 20, 2, 30, 12, 6, 9} 'Это исходный массив

Dim N As Integer = massiv_ishodn.Length - 1 'Это его размер без 1

Dim massiv_rezult(N) As Integer 'Это наш пустой лист бумаги

sortirovka(massiv_ishodn, N, massiv_rezult) 'Сортируем массив

Dim i As Integer

For i = 0 To N

Debug.WriteLine(massiv_rezult(i)) 'Распечатываем отсортированный массив

Next

End Sub

Примечания: В программе вам полезно разобраться самому. Обратите внимание, что в заголовке функции в одном месте вместо ByVal употребляется ByRef. Разберитесь, почему. Обратите внимание, что функция maximum, кроме того, что сама имеет значение максимального элемента массива, выдает еще и порядковый номер максимального элемента – Nomer_max. Это, как я уже говорил, называется побочным эффектом функции.