Пузырьковая сортировка (Bubble-sort)

Подробности: Категория: Сортировка и поиск

Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются $N-1$ раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

Худшее время	$O(n^2)$
Лучшее время	$O(n)$
Среднее время	$O(n^2)$
Затраты памяти	$O(1)$

Пример работы алгоритма

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.

(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как

5>4

(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как

5>2

(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (

8>5

), алгоритм не меняет их местами.

Второй проход:

(1 4 2 5 8) (1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как

4>2

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.

Третий проход:

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

(1 2 4 5 8) (1 2 4 5 8)

Теперь массив отсортирован и алгоритм может быть завершён.

Реализация алгоритма на различных языках программирования:

Синтаксис Intel

mov bx, offset array
    mov cx, n
for_i:
    dec cx
    xor dx, dx
for_j:
    cmp dx, cx
    jae exit_for_j
    jbe no_swap
    mov ah, byte ptr bx[di]
    mov byte ptr bx[di], al
    mov byte ptr bx[si], ah
no_swap:
    inc dx
    jmp for_j
exit_for_j:
    loop    for_i

Синтаксис AT&T (GNU)

.text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
    .type   bubble_sort, @function
bubble_sort:
    mov 8(%esp), %ecx # unsigned length
    cmp $1, %ecx
    jbe exit
    mov 4(%esp), %eax # unsigned *array
    dec %ecx
for_ecx:
    xor %edi, %edi
for_edi:
    mov (%eax,%edi,4), %ebx
    cmp %ebx, 4(%eax,%edi,4)
    jae  no_xchng
    mov 4(%eax,%edi,4), %edx
    mov %edx, (%eax,%edi,4)
    mov %ebx, 4(%eax,%edi,4)
no_xchng:
    inc %edi
    cmp %edi, %ecx
    jne for_edi
    loop for_ecx
exit:
    ret

C

#define SWAP(A, B) { int t = A; A = B; B = t; }
 
void bubblesort(int *a, int n)
{
  int i, j;
 
  for (i = n - 1; i > 0; i--)
  {
    for (j = 0; j < i; j++)
    {
      if (a[j] > a[j + 1])
        SWAP( a[j], a[j + 1] );
    }
  }
}

C++

С использованием Template

#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

Без использования Template

void bubble(int* a, int n)
{
  for (int i = n - 1; i >= 0; i--)
  {
    for (int j = 0; j < i; j++)
    {
      if (a[j] > a[j+1])
      {
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
  }
}

C#

void BubbleSort(int[] A)
{
    for (int i = 0; i < A.Length; i++)
            {
                for (int j = i+1; j < A.Length; j++)
                {
                    if (A[j] < A[i])
                    {
                        var temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                    }
                }
            }
}

Delphi

Сортировка одномерного динамического целочисленного массива:

type
 TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
 var i,p,n: Integer; b: boolean;
begin
 n:= Length(a);
 if n < 2 then exit;
 repeat
  b:= false;
  Dec(n);
  if n > 0 then
  for i:= 0 to n-1 do
   if a[i] > a[i+1] then
    begin
     p:= a[i];
     a[i]:= a[i+1];
     a[i+1]:= p;
     b:= true;
    end;
 until not b;
end;

D

void bubbleSort(alias op, T)(T[] inArray) {
    foreach (i, ref a; inArray) {
        foreach (ref b; inArray[i+1..$]) {
            if (mixin(op)) {
                auto tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
}

Fortran

do i=n-1,1,-1
do j=1,i
    if (a(j).gt.a(j+1)) then
        t=a(j)
        a(j)=a(j+1)
        a(j+1)=t
    endif
enddo
enddo

Java

void bubblesort(int[] arr) {
    for (int i = 0; i < arr.length-1; i++){
        for (int j = i+1; j < arr.length; j++){
            if (arr[i] < arr[j]) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
    }
}

Pascal

for i:=n-1 downto 1 do {n - размер массива M[]}
    for j:=1 to i do
        if M[j]>M[j+1] then
            begin
               tmp:= M[j];
               M[j]:= M[j+1];
               M[j+1]:= tmp;
            end;
write('вывод значений M[]: ');
for i:=1 to n do
    write(M[i]:4);
writeln;

Усовершенствованный алгоритм сортировки пузырьком:

P:=True; {есть перестановка?}
K:=1; {Номер просмотра}
While P Do
Begin
    P:=false;
    For i:=1 To n-k Do
        If X[i] > X[i+1] Then
        Begin
            A:=X[i];
            X[i]:=X[i+1];
            X[i+1]:=A;
            P:=true;
        End;
    k:=k+1;
End;

Perl

for(@out){
  for(0..$N-1){
    if($out[$_]gt$out[$_+1]){
      ($out[$_],$out[$_+1])=($out[$_+1],$out[$_]);
    }
  }
}

Ruby

arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
swap = true
size = arr.length - 1
while swap
  swap = false
  for i in 0...size
    swap |= arr[i] > arr[i + 1]
    arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1]
  end
  size -= 1
end
puts arr.join(' ')
# output => 1 3 3 5 8 10 11 12 17 20

Python

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]
 
def bubble_sort(arr):
    i = len(arr)
    while i > 1:
       for j in xrange(i - 1):
           if arr[j] > arr[j + 1]:
               swap(arr, j, j + 1)
       i -= 1

VBA

Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
    t = False
    For i = 0 To UBound(Mus()) - 1
        If Mus(i) > Mus(i + 1) Then
            tmp = Mus(i)
            Mus(i) = Mus(i + 1)
            Mus(i + 1) = tmp
            t = True
        End If
    Next
Loop
End Sub

PHP

$size = sizeof($arr)-1;
for ($i = $size; $i>=0; $i--) {
    for ($j = 0; $j<=($i-1); $j++)
        if ($arr[$j]>$arr[$j+1]) {
            $k = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $k;
        }
}

JavaScript

function sortBubble(data) {
    var tmp;
 
    for (var i = data.length - 1; i > 0; i--) {
        for (var j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
    return data;
}

JavaFX

function bubbleSort(seq:Number[]):Number[]{
 
    var sort = seq;
    var elem:Number;
 
    for(n in reverse [0..sizeof seq - 2]){
        for(i in [0..n] ){
            if(sort[i+1] < sort[i] ){
                elem = sort[i];
                sort[i] = sort[i+1];
                sort[i+1] = elem;
            }
        }
    }
 
    return sort;
}

Nemerle

using System.Console;
using Nemerle.Collections;
 
def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3];
 
foreach (i in [0..arr.Length-1])
    foreach (j in [0..arr.Length-2])
       when (arr[j] > arr[j+1])
           (arr[j], arr[j+1]) = (arr[j+1], arr[j]);
 
WriteLine($"Sorted list is a $(arr.ToList())");

TurboBasic 1.1

CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456
 
PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"
 
FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT
 
PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"
 
PRINT " SLUCHAINYE CHISLA"
 
FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT
 
PRINT " PEREMESHANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
 
'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1
      IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
 
      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y[X1];               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM
 
   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER
 
PRINT " OTSORTIROVANNYJ MASSIV"
 
FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).

При написании статьи были использованы открытые источники сети интернет :

Wikipedia

Kvodo

Youtube