Сортировка пузырьком
Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.
Идея алгоритма заключается в следующем. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера (рис. 6.1) рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов n которого равно 5: 9, 1, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений.
Рисунок 6.1 – Пример пузырьковой сортировки
Вначале сравниваются два первых элемента последовательности: 9 и 1. Так как значение первого элемента больше значения второго, т. е. 9>1, они меняются местами. Далее, сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется n*(n-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.
Код программы на C++:
int i, j, count, key;
void BubbleSort(int A[], int n) //сортировка пузырьком
{
for (i=0; i<n-1; i++)
{
for (j=1; j<n; j++)
{
key=j;
count=A[j-1];
if (A[key-1]>A[j])
{
A[key-1]=A[j];
A[j]=count;
}
}
}
cout<<"Результирующий массив: ";
for (i=0; i<n; i++) cout<<A[i]<<" "; //вывод массива
}
void main () //главная функция
{
int n; int A[1000];
cout<<"Количество элементов > "; cin>>n;
for (i=0; i<n; i++) //ввод массива
{ cout<<i+1<<" элемент > "; cin>>A[i]; }
BubbleSort(A, n);
}
Код программы на Pascal:
type arr=array[1..1000] of integer;
var A: arr;
n, i, j: integer;
procedure BubbleSort(A: arr; n: integer); {сортировка пузырьком}
var key, count: integer;
begin
for i:=1 to n do
begin
for j:=1 to n-1 do
begin
key:=j;
count:=A[j];
if A[key]>A[j+1] then
begin
A[key]:=A[j+1];
A[j+1]:=count;
end
end
end;
write('Результирующий массив: ');
for i:=1 to n do write(A[i],' '); {вывод массива}
end;
begin {основной блок программы}
write('Количество элементов > '); read(n);
for i:=1 to n do {ввод массива}
begin write(i, ' элемент > '); read(A[i]); end;
BubbleSort(A, n);
end.
Приведенный код можно улучшить, а именно – вдвое уменьшить количество выполняемых сравнений. Для этого достаточно с каждым шагом i внешнего цикла на i уменьшать количество итераций внутреннего цикла. Ниже показан основной фрагмент алгоритма обменной сортировки для языков C++ и Pascal, его улучшенный вариант.
Код программы на C++:
for (i=0; i<n-1; i++)
{
for (j=0; j<n-(i+1); j++)
{
key=j+1;
count=A[key];
if (A[j]>A[key])
{
A[key]=A[j];
A[j]=count;
}
}
}
Код программы на Pascal:
for i:=1 to n-1 do
begin
for j:=1 to n-i do
begin
key:=j+1;
count:=A[key];
if A[j]>A[key] then
begin
A[key]:=A[j];
A[j]:=count;
end
end
end;
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).