Bubble Sort

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]

 


Associação SoftwareLivre

A Associação SoftwareLivre.org (ASL) é uma associação civil sem fins-lucrativos, com sede em Porto Alegre/RS que reúne empresários, profissionais liberais, estudantes e servidores públicos, estabelecendo relações com os mais diversos setores da sociedade como o poder público, universidades, empresas, grupos de usuários, hackers e ONGs. A ASL tem por principal objetivo tornar o software livre amplamente incluído na sociedade, propiciando espaço de discussão, apoio, fomento e organização de iniciativas nas mais diversas áreas relacionadas. - Site oficial da associação