Конференция VBStreets

Алгоритм сортировки пузырьком является одним из самых простых алгоритмов сортировки. Однако, эффективность этого алгоритма значительно снижается с увеличением объёма данных, подлежащий сортировке.

Сложность алгоритма: 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


Если не ошибаюсь, Oxygen как-то выкладывала неплохой обзор методов сортировки. Ее пост найти не могу, но кое-что сохранилось.