Пузырьковая сортировка

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками.

Алгоритм

Пример сортировки пузырьком списка случайных чисел.

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

Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка.

Примеры реализации

Псевдокод

function bubblesort (A : list[1..n]) {
    var int i, j;
    for i from n downto 2 {
        for j from 1 to i-1 { 
            if (A[j] > A[j+1])
                swap(A[j], A[j+1])
        }
    }
}

Assembler

	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

GNU Assembler

.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) {A=A^B;B=A^B;A=A^B;}
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++

#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 );
}

C#

void BubbleSort(ref int[] a)
{
    for(int i = a.Length - 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]; {{1}}
		a[j+1] = tmp;
	    }
}

Delphi

Сортировка одномерного динамического целочисленного массива:
 
type
 TIntVec = array of Integer; 
...
procedure BubbleSort(var a: TIntVec);
 var i,p,n: Integer; b: boolean;
begin
 n:= Length(a)-1;
 if n < 1 then exit;
 repeat
  b:= true;
  Dec(n);
  for i:= 0 to n do
   if a[i] > a[i+1] then
    begin
     p:= a[i];
     a[i]:= a[i+1];
     a[i+1]:= p;
     b:= false;
    end;
 until b;
end;

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 swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j]; 
    arr[j] = t;
}
 
void bubblesort(int[] arr){
    for(int i = arr.length-1 ; i >= 0 ; i--){
        for(int j = 0 ; j < i ; j++){
            if( arr[j] > arr[j+1] )
               swap(arr, j, j+1);
        }
    }
}

Pascal

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

arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
 
swap = 1
 
while swap > 0
 
  swap = 0
 
  for i in 0..arr.length - 1
 
    break if arr[i + 1] == nil
 
    swap += 1 if arr[i] > arr[i + 1]
 
    arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1]
 
  end
 
end
 
puts "#{arr.join(" ")}"
# output => 1 3 3 5 8 10 11 12 17 20