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.

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 pseudo-có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 Vvem depois de V[i + 1
6                   então troque Ve V[i + 1 de lugar e
7                         houveTroca <- verdade

Implementações

C

  void bubble(int x^*,int n)
  {
    int troca, i, j, aux;
    for (i = n-1; i > 0; i--)
    {
      // o maior valor entre xe x^*
      troca = 0;     
      for (j =0 ; j < i; j++)
      {
        if (x> x[j+1)
        {
          aux = x^*;
          x= x[j+1;
          x^* = aux;
          troca = 1;
        }
      }
      if (!troca) return;
    }
  }

C++

template
void bubble_sort( std::vector &lista )
{
  std::vector::reverse_iterator it1;
  for( it1 = lista.rbegin(); it1 != lista.rend(); ++it1 )
  {
    std::vector::iterator it2;
    bool troca = false;
    for( it2 = lista.begin(); &*it2 != &*it1; ++it2 )
    {
      if ( *it2 > *(it2+1) )
      {
        std::iter_swap( it2, it2+1 );
        troca = true;
      }
    }
    if( !troca )
    {
      return;
    }
  }
}

Java

public static void Bolha (int^* v)
{
   for (int i = v.length - 1; i > 0; i--)
   {
      for (int j = 0; j < i; j++)
         if (v > v [j + 1)
            troca (v, j, j + 1);
   }
}
public static void troca (int^* v, int j, int aposJ)
{
   int aux = 0;
   aux = v ^*;
   v = v [aposJ;
   v ^* = aux;
}

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^*of integer;
    i,j,aux: integer;
  begin
    {Preenche o array com valores aleatórios}
    for i := 1 to n do
      vet^* := random(100);
    {Ordena o array}
    for i := n downto 2 do
         for j := 1 to i-1 do
            if vet> vet[i+1 then 
            begin
                aux := vet^*;
                vet:= vet[j+1;
                vet^* := aux;
            end;      
  end.
{Atenção cuidar os erros!}

Python

def bubblesort(l):
    for passesLeft in range(len(l)-1, 0, -1):
        for index in range(passesLeft):
            if l< l[index + 1:
               ll+ 1, l[index" target="_blank" >^*
    return l

Perl

sub swap {
  ($_$_^*," target="_blank" >$_[0);
}
sub bubble_sort {
  for ($i=$|; $i < $#_; ++$i) {
    for ($j=$|; $j < $#_; ++$j) {
      ($_> $ _^*," target="_blank" >$_[$j+1);
    }
  }
}

C#


       private intBubbleSort1(int[ vetor)                //retorna a array ordenada
        {
            for (int i = 0; i < vetor.Length; i++)
            {
                for (int j = 0; j < vetor.Length - 1; j++)
                {
                    if (vetor> vetor[j + 1)
                    {
                        int swap   = vetor^*;
                        vetor  = vetor[j+1;
                        vetor^* = swap;
                    }
                }
            }
            return vetor;
        }

PHP

        > $arrToSort[$j) {
                    swap($arrToSort$arrToSort[$j);
                }
            }
        }
        
        /* Opcional. Exibe o array de um jeito que nós podemos entender! =D */
        print_r($arrToSort);
        ?>

Shell_script

!/bin/bash
 Criado em:Qua 12/Jul/2006 hs 12:34
 Last Change: Qua 12 Jul 2006 12:57:59 BRT
 Instituicao:
 Proposito do script: algoritimo de ordenação
echo " Digite cinco numeros!"
for ((i=0; i<=4; i++)); do
	read n^*
done
     
              for ((i=0; i<=3; i++)); do
                for ((j=i+1; j<=4; j++)) do
                
                    if ${n^*}" target="_blank" >; then
                     
                            x=${n^*}
                            n^*=${n^*}
		            n^*=$x 
		     fi
		   
		 done
	      done
 
echo "Lista ordenada!" 
for ((i=0; i<=4; i++)); do
    echo  digitado ${n^*}
done

Algoritmos | algoritmos de ordenação

Gourt Home::Gourt :: Bubble sort

Implementações