Сложность алгоритма: O(n^2)
Суть алгоритма сортировки пузырьком в том, что элементы сортируемой последовательности рассматриваются попарно: два стоящий рядом элемента. Если эти два элемента стоят в неверном порядке, они меняются местами.
Когда БИ проходит по всем парам, цикл (перестановок) повторяется. Если при этом БИ не приходится менять местами ни одну из пар (все т.е. элементы стоят в нужном порядке) - последовательность считается отсортированной.
Пример в псевдокоде:
- Код: Выделить всё
list[0 to 100] // последовательность, заполнненная числами (неотсортированная)
var bSwapped
var i
SortLoop:
bSwapped = False
for i = 0 to 100 - 1
if list[i] > list[i+1] then
bSwapped = True
swap(list[i], list[i+1]) // Меняем местами значение элементов последовательности
end if
next i
if bSwapped = True then goto SortLoop
Реализация алгоритма пузырьковой сортировки на VB:
- Код: Выделить всё
Public Sub Swap(ByRef a As Long, ByRef b As Long)
Dim c As Long
c = a
a = b
b = c
End Sub
Public Sub BubbleSort(ByRef SortArray() As Long)
Dim i As Long
Dim bSwapped As Boolean
Do
bSwapped = False
For i = LBound(SortArray) To UBound(SortArray) - 1
If SortArray(i) > SortArray(i + 1) Then
bSwapped = True
Swap SortArray(i), SortArray(i + 1)
End If
Next i
Loop While bSwapped
End Sub
Этот код сортирует последовательность в порядке возрастания. Для того, чтобы он сортировал последовательность в порядке убывания, необходимо в строке [ If SortArray(i) > SortArray(i + 1) Then] заменить оператор > на оператор <.
Пример использования:
- Код: Выделить всё
Dim foo(1 To 10) As Long
foo(1) = 10
foo(2) = 1
foo(3) = 9
foo(4) = 2
foo(5) = 8
foo(6) = 3
foo(7) = 7
foo(8) = 4
foo(9) = 5
foo(10) = 6
BubbleSort ega
For i = 1 To 10
Debug.Print foo(i)
Next i
