21 FreeBASIC - сортировка пузырьком

Рассмотрим самый простой метод сортировки - метод сортировки пузырьком. Его ещё называют сортировка простыми обменами или сортировка пузырьком.

При просмотре(проходе) массива его элементы попарно сравниваются и если пара не упорядочена - элементы меняются местами. Так происходит до тех пор пока такая перестановка нужна. Но как же узнать нужна она или нет? Всё просто если при очередном проходе никакие элементы не обменялись значениями(не переставились) значит и последующий проход не нужен - элементы упорядочены.

При каждом проходе можно заметить (сортировка по возрастанию, например) что наибольший элемент смещается в конец массива, а наименьший перемещается в направлении к началу на один шаг. Отсюда и название метода - легкие элементы всплывают, как пузырьки.

Массив на видео: 3,0,1,8,7,2,5,4,6,9

Сначала проверяется первая пара a[0]=3 и a[1]=0, здесь a[0]>a1 следовательно они меняются местами.

Теперь проверяется следующая пара a[1]=3 и a[2]=1, здесь a[1]>a2 следовательно и они меняются местами, здесь a[1] уже равно 3, a[1] и a[0] обменялись значениями на предыдущем шаге.

При сравнении a[2] и a[3], здесь условие a[2]>a3 не выполняется, следовательно значения элементов местами не меняются.

a[3]=8 и a[4]=7(8>7) - меняются местами

a[4]=8 и a[5]=2(8>2) - меняются местами

a[5]=8 и a[6]=5(8>5) - меняются местами

a[6]=8 и a[7]=4(8>4) - меняются местами

a[7]=8 и a[8]=6(8>6) - меняются местами

и лишь в последнем случае a[8]=8 и a[9]=9(8 не больше 9) - не меняются местами

видно как 8-элемент массива a[3] переместился на позицию a[8]
Первый проход цикла завершён, а так как элементы переставлялись - просмотрим массив ещё раз.

Пары a[0] и a[1],

a[1] и a[2],

a[2] и a[3] упорядочены

и лишь добравшись до a[3] и a[4], переставляем элементы местами. И наблюдаем как с каждым шагом "7" перемещается к "8"

И так далее - после второго прохода пошёл третий...

...пока все элементы не оказались на своих местах.

dim shared as integer a(0 to 9)=>{3,0,1,8,7,2,5,4,6,9}
dim as integer i, j, flag

sub printb
    dim k as integer
    for k =0 to 9
        print a(k);
    next k
    print
end sub

printb
print

do
    flag=0
    for i=0 to 8
        if a(i+1)<a(i) then swap a(i),a(i+1):flag=1
    next i
    printb
loop while flag=1

sleep

Массив отсортирован за четыре прохода, четвёртый проход был сделан чтобы убедиться что перестановок больше не было и массив отсортирован.

Способ сортировки методом пузырька очень прост и в то же время очень ресурсоёмок. при большом количестве элементов сортировка занимает очень большое время. Этот способ рассматривается лишь в качестве примера при обучении.