[Описание] Сортировка пузырьком.

Различные алгоритмы сортировки.
Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16086
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

[Описание] Сортировка пузырьком.

Сообщение Хакер » 28.12.2007 (Пт) 16:39

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

Сложность алгоритма: 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
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

alibek
Большой Человек
Большой Человек
 
Сообщения: 14099
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Сообщение alibek » 28.12.2007 (Пт) 16:50

Если не ошибаюсь, Oxygen как-то выкладывала неплохой обзор методов сортировки. Ее пост найти не могу, но кое-что сохранилось.
Вложения
sorting.zip
Алгоритмы сортировки
(41.91 Кб) Скачиваний: 298
Lasciate ogni speranza, voi ch'entrate.


Вернуться в Сортировка

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList