Сортировка пузырьком
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n2).
АлгоритмАлгоритм состоит в повторяющихся проходах по сортируемому массиву. За
каждый проход элементы последовательно сравниваются попарно и, если
порядок в паре неверный, выполняется обмен элементов. Проходы по
массиву повторяются до тех пор, пока на очередном проходе не окажется,
что обмены больше не нужны, что означает — массив отсортирован. При
проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до
нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Реализация на 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
|
Литература
|
