2. Линейная сортировка массива

Существует множество алгоритмов для сортировки массивов. Рассмотрим два алгоритма: сортировка выбором и метод пузырька.

Cортировка выбором. Суть метода может быть описана так:

1. В последовательности из n элементов выбирается наименьший (наибольший) элемент;

2. Меняется местом с первым;

3. Далее процесс повторяется с оставшимися n-1 элементами, затем с оставшимися n-2 элементами и т.д., до тех пор, пока не останется один самый большой (маленький) элемент.

Для реализации этого алгоритма необходимо использовать два вложенных цикла с параметром For. Внешний цикл (по i) предназначен для последовательного фиксирования элементов массива, внутренний (по j) – осуществляет поиск минимального (максимального) и его позиции в неотсортированной части массива. После выхода из внутреннего цикла следует перестановка элементов. Последний элемент во внешнем цикле не рассматривается: он сам встанет на свое место.

Фрагмент программного кода процедуры сортировки выбором: (нумерация элементов массива начинается с единицы):

For i = 1 To n - 1 'Внешний цикл: перебор элементов массива

Min = a(i): nom = i 'Сортировка по убыванию

For j = i + 1 To n 'Внешний цикл: поиск минимального элемента и

'его позиции в неотсортированной части массива

If (a(j) < Min) Then Min = a(j): nom = j

Next j

tmp = a(i) 'Перестановка элементов a_i и a_nom

a(i) = a(nom)

a(nom) = tmp

Next i

For i = 1 To n

Text3.Text = Text3.Text + " " + Str(a(i))

Next i

Сортировка методом пузырька. Метод основан на сравнении соседних элементов. «Неправильно» расположенные по отношению друг к другу элементы меняются местами. Во вложенных циклах поочередно фиксируется пара соседних элементов массива. В результате первого прохода элемент с минимальным значением оказывается в первой позиции массива (всплывает) (Рис. 6).

Рис. 6 – Сортировка методом пузырька

Фрагмент программного кода сортировки методом пузырька:

Const n = 10

Dim a(1 To n) As Byte

Private Sub Command1_Click()

Randomize

For i = 1 To n

a(i) = Int(Rnd * 40)

Picture1.Print a(i)

Next i

End Sub

Private Sub Command2_Click()

Dim r As Byte

For i = 1 To n-1 'Цикл по числу проходов

For j = 1 To n – i 'Цикл для сравнения соседних

'элементов в оставшейся части массива

If a(j) > a(j + 1) Then 'Сравнение соседних элементов

r = a(j)

a(j) = a(j + 1) 'Перестановка элементов a_j и a_j+1

a(j + 1) = r

End If

Next j

Next i

For i = 1 To n

Picture2.Print a(i)

Next i

End Sub