O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A idéia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o menor elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
No melhor caso, o algoritmo executa n2 / 2 operações relevante, onde n representa o número de elementos do vetor. No piores casos são feitas 2n2 operações. No caso médio, são feitas 5n2 / 2 operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
O algoritmo pode ser descrito em pseudocódigo como segue abaixo. V é um VETOR de elementos que podem ser comparados e n é o tamanho desse vetor.
BUBBLESORT (V[], n)
1 houveTroca <- verdade # uma variável de controle
2 enquanto houveTroca for verdade faça
3 houveTroca <- falso
4 para i de 1 até n-1 faça
5 se V[i] vem depois de V[i + 1]
6 então troque V[i] e V[i + 1] de lugar e
7 houveTroca <- verdade
■ Implementações
► Assembly
/*void bubble_as2 (int *x, int n);*/
.globl bubble_as2
/* assembler utilizado gas (x86 - Linux) */
bubble_as2:
pushl %ebp
movl %esp, %ebp
movl 12(%ebp), %eax /* tamanho -> %eax */
movl 8(%ebp), %ecx /* início do vetor -> %ecx */
movl $4, %ebx
dec %eax
mul %ebx
addl %eax, %ecx /* %ecx aponta p/ o*/
/*último do elemento do vetor */
pushl %ecx
_bubble_as2_l1:
movl $0, %edx
movl 8(%ebp), %ebx
movl %ebx, %eax
addl $4, %eax
_bubble_as2_l2:
cmp %eax, %ecx
jl _bubble_as2_l1_end
movl (%ebx), %ecx
cmp (%eax), %ecx
jl _bubble_as2_l2_end
/* troca */
movl (%eax), %edx
movl %edx, (%ebx)
movl %ecx, (%eax)
movl $1, %edx
_bubble_as2_l2_end:
movl %eax, %ebx
addl $4, %eax
movl (%esp), %ecx
jmp _bubble_as2_l2
_bubble_as2_l1_end:
cmp $0, %edx
je _bubble_as2_fim
popl %ecx
subl $4, %ecx
pushl %ecx
jmp _bubble_as2_l1
_bubble_as2_fim:
leave
ret
► C
Com 10 elementos o Bubble simples usa 100 iterações, no segundo for, e esse usa apenas 55.
void bubble( int v[], int qtd )
{
int i;
int j;
int aux;
int k = qtd - 1 ;
for(i = 0; i < qtd; i++)
{
for(j = 0; j < k; j++)
{
if(v[j] > v[j+1])
{
aux = v[j];
v[j] = v[j+1];
v[j+1]=aux;
}
}
k--;
}
}
► C
Usando for ao invés de do...while
void swapbubble( int v[], int i )
{
aux = v[i];
v[i] = v[i+1];
v[i+1]=aux;
}
void bubble( int v[], int qtd )
{
int i,j;
for( j = 0; j < qtd; j++ )
{
for( i = 0; i < qtd - 1; i++ )
{
if( v[i] > v[i+1] )
{
swapbubble( v, i );
}
}
}
}
void swapbubble( int v[], int i)
{
int aux=0;
aux=v[i];
v[i] = v[i+1];
v[i+1] = aux;
}
void bubble(int v[], int qtd)
{
int i;
int trocou;
do
{
qtd--;
trocou = 0;
for(i = 0; i < qtd; i++)
if(v[i] > v[i + 1])
{
swapbubble(v, i);
trocou = 1;
}
}while(trocou);
}
■ Implementações Método de ordenação Bolha com ordenação de strings.
void bubble(int v[], int qtd)
//UTILIZA BIBLIOTECA string.h
{
int i;
int trocou;
char aux;
do
{
qtd--;
trocou = 0;
for(i = 0; i < qtd; i++)
if(strcasecmp(v[i],v[i + 1])>0)
{
/*o ideal seria fazer uma função troca aqui*/
strcpy(aux, v[i]);
strcpy(v[i], v[i + 1]);
strcpy(v[i + 1], aux);
trocou = 1;
}
}while(trocou==1);
}
► C++
include "Bubblesort.h"
void bubblesort(vetor &a, tamanho n) { for(indice j= n-1; j>=n; j--)
for(i=0;i
► Java
public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length-1; i++) {
for (int j = 0; j < a.length-i-1; j++) {
if (a[j] > a[j+1]) {
swap(a, j, j+1);
}
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
► ML
fun fix ( f,x) =
let val fx = f(x)
in
if x = fx then x
else fix(f,fx)
end;
fun bubble ([]) = []
| bubble([a]) = [a]
| bubble(a::b::x) =
if a <= b then a::bubble(b::x)
else b::bubble(a::x);
fun bubblesort( lista ) = fix (bubble,lista);
► Pascal
O código a seguir ilustra o algoritmo, para ordenar n números inteiros:
program ordenacao;
uses crt;
const
n = 20;
var
vet:array[1..n]of integer;
i,j,aux: integer;
begin
randomize;
{Preenche o array com valores aleatórios}
for i := 1 to n do
vet[i] := random(100);
{Ordena o array}
for i := n downto 2 do
for j := 1 to i-1 do
if vet[j] > vet[j+1] then
begin
aux := vet[j];
vet[j] := vet[j+1];
vet[j+1] := aux;
end;
end.
► Python
def bubblesort(l):
for passesLeft in range(len(l)-1, 0, -1):
for index in range(passesLeft):
if l[index] < l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l
► Perl
sub swap {
($_[0], $_[1]) = ($_[1], $_[0]);
}
sub bubble_sort {
for ($i=$|; $i < $#_; ++$i) {
for ($j=$|; $j < $#_; ++$j) {
($_[$j] > $ _[$j+1]) && swap($_[$j], $_[$j+1]);
}
}
}
► C#
private void BubbleSort(int[] vetor)
{
for (int i = vetor.Length - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (vetor[j] > vetor[j + 1])
{
int swap = vetor[j];
vetor[j] = vetor[j+1];
vetor[j+1] = swap;
}
}
}
}
► PHP
<?php
/*
Esta função troca o valor de duas variáveis entre si.
Opcional. Pode ser embutido na bolha
*/
function swap(&$valor_1, &$valor_2) {
$valor_1_antigo = $valor_1;
$valor_2_antigo = $valor_2;
$valor_1 = $valor_2_antigo;
$valor_2 = $valor_1_antigo;
}
/* Array de teste */
$arrToSort = array(1, 4, 7, 3, 8, 9, 10);
/* a BOLHA! ;-) */
for ($i = 0; $i < count($arrToSort); $i++) {
for ($j = $i; $j < count($arrToSort); $j++) {
if ($arrToSort[$i] > $arrToSort[$j]) {
swap($arrToSort[$i], $arrToSort[$j]);
}
}
}
/* Opcional. Exibe o array de um jeito*/
/*que nós podemos entender! =D */
print_r($arrToSort);
?>
<?php
function BubbleSort( $items ) {
$temp = "";
$size = count( $items );
for( $i = 1; $i < $size; $i++ ) {
for( $j = 1; $j < $size - $i; $j++ ) {
if( $items[$j+1] < $items[$j] ) {
$temp = $items[$j];
$items[$j] = $items[$j+1];
$items[$j+1] = $temp;
}
}
}
}
$items = array(31, 41, 59, 26, 41, 58);
BubbleSort( $items );
?>
► Shell_script
#!/bin/bash
# Criado em:Qui 31/Jul/2008 hs 12:34
# Last Change: Qui 31 Jul 2008 12:57:59 BRT
# Instituição:
# Propósito do script: algoritimo de ordenação
echo " Digite cinco números"
for ((i=0; i<=4; i++)); do
read n[i]
done
for ((i=0; i<=3; i++)); do
for ((j=i+1; j<=4; j++)) do
if [ ${n[i]} -gt ${n[j]} ]; then
x=${n[i]}
n[i]=${n[j]}
n[j]=$x
fi
done
done
echo "Lista ordenada!"
for ((i=0; i<=4; i++)); do
echo digitado ${n[i]}
done
► Matlab
for(i = 1:n)
for(j = 1:n-1)
if(x(j) > x(j + 1))
aux = x(j);
x(j) = x(j + 1);
x(j + 1) = aux;
end
end
end
► ASP
<%
Dim links(5)
links(0) = 1
links(1) = 3
links(2) = 5
links(3) = 2
links(4) = 4
'Esta função troca o valor de duas variáveis entre si.
'Opcional. Pode ser embutido na bolha
function swap(i, j)
valor_1_antigo = links(i)
valor_2_antigo = links(j)
links(i) = valor_2_antigo
links(j) = valor_1_antigo
end Function
'A BOLHA
for i = 0 to UBound(links)
for j = i+1 to UBound(links)
if (links(i) > links(j)) then
call swap(i, j) 'Passa o ponteiro para a
funcao swap
end if
next
next
'Resultado
for i = 0 to UBound(links)
Response.write links(i) & " "
next
%>
[Topo]