Сортировка пузырьком

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

Алгоритм

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

Реализация на 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]);
}

Реализация на 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);
}

Реализация на PHP

for ($i = (count($arr)-1); $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;
 }
}

Реализация на Pascal

for i := n - 1 downto 1 do
 for j := 1 to i do
 if a[j] > a[j+1] then
 begin
 t := a[j];
 a[j] := a[j+1];
 a[j+1] := t;
 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

Литература

Ананий В. Левитин Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 144-146.
Википедия


Алгоритмы сортировок и их реализации
	Главная