Bubble sort – Wikipédia a enciclopédia livre

Prévia do material em texto

Bubble sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior
caso
complexidade caso
médio
complexidade
melhor caso
complexidade de
espaços pior caso
 auxiliar
Algoritmos
Bubble sort
Origem: Wikipédia, a enciclopédia livre.
Índice
1 Introdução
2 Algoritmo
2.1 Pseudo-código
2.2 Demonstração de corretude
2.3 Análise do consumo de tempo
2.4 Versão alternativa
3 Implementação
3.1 Assembly
3.2 C
3.3 Java
3.4 ActionScript 3
3.5 C
3.6 C++
3.7 ML
3.8 Pascal
3.9 Python
3.10 Ruby
3.11 Perl
3.12 C#
3.13 PHP
3.14 Shell script
3.15 Lua
3.16 Matlab
3.17 R
3.18 ASP
3.19 JavaScript
3.20 Visual Basic
4 Fluxograma
5 Ver também
6 Ligações externas
Introdução
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais
simples. A ideia é percorrer o vector diversas vezes, a cada passagem fazendo flutuar para o topo o maior
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 operações relevantes, onde n representa o número de elementos do
vector. No pior caso, são feitas 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.
Algoritmo
Pseudo-código
O algoritmo abaixo, descrito em pseudo-código, promete ordenar um vetor V[1..n] em ordem crescente.
Algoritmo Bubble(V, n)
1. k = n-1
2. para i = 1 até n faça
3. j = 1
4. enquanto j <= k faça
5. se V[j] > V[j+1] então
6. aux = V[j]
7. V[j] = V[j+1]
8. V[j+1] = aux
9. j = j+1
10. k = k-1
Demonstração de corretude
A demonstração do algoritmo se apóia nos seguintes invariantes, provados por indução matemática:
(i0): na linha 2, V[n-i+2 .. n] é crescente.
Prova: no momento da entrada do laço externo, quando i=1, o invariante vale, já que V[n+1 .. n] é vazio e,
portanto, crescente. Suponha agora que o invariante vale se trocarmos i por i-1. Queremos mostrar que ele
também vale para i. Por hipótese de indução, V[n-i+3 .. n] é crescente. Pelo invariante (i1), ao terminar o laço
das linhas 4-9, teremos que V[1 .. n-i] <= V[n-i+1]. V[n-i+2] <= V[n-i+3 .. n]. Assim, V[n-i+2 .. n] é
crescente.
Observe que a validade de (i0) em conjunto com a condição de parada do algoritmo (i = n+1) implicam na
corretude do mesmo: V[n-(n+1)+2 .. n] = V[1 .. n] é crescente.
(i1): na linha 4, vale que V[ j ] >= V[1 .. j-1]
Prova: o invariante vale na entrada do laço das linhas 4-9, quando j=1, pois V[1] >= V[1..0] (vazio). Suponha
agora que o invariante vale se trocarmos j por j-1. Então, V[ j-1 ] >= V[1 .. j-2] na linha 4. Ora, mas podemos
ver que, ao final do laço interno, V[ j ] >= V[ j-1 ]. De fato, na linha 5, se V[ j-1 ] > V[ (j-1)+1 ] = V[ j ],
trocaremos V[ j-1 ] e V[ j ] de posição, o que garante que V[ j ] >= V[ j-1 ] sob qualquer circunstância.
Observe que, ao final do laço interno, V[n-i+1] >= V[1 .. n-i]: aplique (i1) com j = k+1, notando que k = n-i.
Análise do consumo de tempo
TODO. Alguém saberia formatar melhor esta tabela?
-------------+-------------------------------------
 linha | número de execuções da linha
-------------+-------------------------------------
 1 1
 2 n+1
 3 n
 4 n
 5 sum_{i=1}^{n} n-i+1 = (n^2 + n)/2 + 1
 6 <= sum_{i=1}^{n} n-i = (n^2 + n)/2
 7 <= sum_{i=1}^{n} n-i = (n^2 + n)/2
 8 <= sum_{i=1}^{n} n-i = (n^2 + n)/2
 9 sum_{i=1}^{n} n-i = (n^2 + n)/2
 10 n
-------------+-------------------------------------
 total <= (5/2)n^2 + (13/2)n + 3
-------------+-------------------------------------
O consumo de tempo de Bubble é \theta(n^2).
TODO: provar.
Versão alternativa
Abaixo há um algoritmo Bubble Sort onde a implementação é a mais simples possível, ou seja, é a
versão original do Bubble Sort sem o aprimoramento da variável "houve troca".
BUBBLESORT (V[], n)
 houveTroca <- verdade # uma variável de controle
 enquanto houveTroca for verdade faça:
 houveTroca <- falso
 para i de 1 até n-1 faça:
 se V[i] vem depois de V[i + 1]
 então troque V[i] e V[i + 1] de lugar e
 houveTroca <- verdade
 Para j de 1 até (i - 1) Passo 1
 Se a[j - 1] > a[j] Então
 aux <- a[j]
 a[j] <- a[j - 1]
 a[j - 1] <- aux
 FimSe
Observação: Neste algoritmo tanto o melhor caso, como o pior caso tem ordem "n²", porque em ambos
os casos os ciclos são sempre realizados até ao fim, mesmo quando os elementos já estão ordenados.
Implementação
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
 retts
C
1. include<stdio.h>
2. include<stdlib.h>
3. include<conio.h>
4. include<stdbool.h>
int main() {
 int vetor[5], i, aux;
 
 bool parar = false;
 
 for(i=0;i<5;++i)
 {
 printf("Digite o valor: ");
 scanf("%d",&vetor[i]);
 }
 
 while(parar == false)
 {
 parar = true;
 
 for(i=0;i<4;++i)
 {
 if(vetor[i]>vetor[i+1])
 {
 parar = false;
 aux = vetor[i];
 vetor[i] = vetor[i+1];
 vetor[i+1] = aux;
 }
 }
 }
 
 for(i=0;i<5;++i)
 {
 printf("%d",vetor[i]);
 }
 
 getch();
 return 0;
}
Java
public static void bubbleSort (int [] vetor){
 
 boolean houveTroca = true;
 
 while (houveTroca) {
 houveTroca = false;
 for (int i = 0; i < (vetor.length)-1; i++){
 if (vetor[i] > vetor[i+1]){
 int variavelAuxiliar = vetor[i+1];
 vetor[i+1] = vetor[i];
 vetor[i] = variavelAuxiliar;
 houveTroca = true;
 }
 }
 } 
}
ActionScript 3
function bubbleSort (v:Array):void
{
 for (var i:int = v.length; i >= 1; i--)
 {
 for (var j:int = 1; j < i; j++)
 {
 if (v[j - 1] > v[j])
 {
 var aux:int = v[j];
 v[j] = v[j - 1];
 v[j - 1] = aux;
 }
 }
 }
}
C
Usando "do while".
void swapbubble( int v[], int i)
{
 
int aux=0; 
 
 aux=v[i];
 v[i] = v[i+1];
 v[i+1] = aux;
 
}
 
 voidbubble(int v[], int qtd)
{
 int i;
 int trocou;
 
 qtd--;
 do
 {
 trocou = 0;
 for(i = 0; i < qtd; i++)
 {
 if(v[i] > v[i + 1])
 {
 swapbubble(v, i);
 trocou = 1;
 }
 }
 }while(trocou);
}
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 <algorithm>
using namespace std;
 
void bubblesort(int a[], int n)
{
 for(int j=0; j<n; j++){
 for(int i=0; i<n-1; i++){
 if(a[i+1] < a[i])
 swap(a[i+1], a[i]);
 }
 }
}
ML
http://pt.wikipedia.org/skins-1.5/common/images/button_hr.png
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 bubble_sort;
 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.
Implementação do Algoritmo Bolha com FLag
program BolhacomFLag;
uses wincrt;
const
n=10;
 var
 vet:array[1..n] of integer;
 i,aux:integer;
 houveTroca:boolean;
 begin
 i:=0;
 houveTroca:=true;
 randomize;
 for i:=1 to n do
 vet[i]:=random(100);
 for i:=1 to n do
 writeln(vet[i]);
 repeat
 houveTroca:=false;
 for i:=1 to n-1 do
 if ( vet[i] > vet[i+1]) then
 begin
 aux := vet[i];
 vet[i]:= vet[i+1];
 vet[i+1]:= aux;
 houveTroca:=true;
 end;
 until (houveTroca = false);
 writeln('Escrevendo Vetor Ordenado');
 for i:=1 to n do 
 writeln(vet[i]);
 {by X}
 end.
Método Bolha com StringList
 var
 a,b,ind: Integer;
 aux: String;
 sListaEx: TStringList; 
 begin
 sListaEx.add(String);
 for a := 0 to sListaEx.count -1 do
 begin
 for b := 0 to sListaEx.count -1 do
 begin
 if sListaEx[a] < sListaEx[b] then
 begin
 aux := sListaEx[a];
 sListaEx[a] := sListaEx[b];
 sListaEx[b] := aux;
 end;
 end;
 end;
 sListaEx := TStringList.Create;
 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
def bubbleSort(L,n):
 flag = True
 while flag:
 flag = False
 for i in range(n-1):
 if L[i] > L[i+1]:
 L[i],L[i+1] = L[i+1],L[i]
 flag = True
Ruby
def bubble_sort(list)
 swapped = true
 while swapped
 swapped = false
 (list.size - 1).times do |i|
 if list[i] > list[i+1]
 list[i], list[i+1] = list[i+1], list[i]
 swapped = true
 end
 end
 end
 
 list
end
Perl
sub swap {
 @_[0, 1] = @_[1, 0];
}
sub bubble_sort {
 for ($i=$|; $i < $#_; ++$i) {
 for ($j=$|; $j < $#_; ++$j) {
 ($_[$j] > $ _[$j+1]) and swap($_[$j], $_[$j+1]);
 }
 }
}
C#
 private void BubbleSort(int[] vetor)
 {
 
 //Ordem Decrescente!
 
 for (int i = vetor.Length - 1; i > 0; i--)
 {
 for (int j = 0; j < i; j++)
 {
 if (vetor[i] > vetor[j])
 {
 int swap = vetor[i];
 vetor[i] = vetor[j];
 vetor[j] = swap;
 
 }
 }
 }
 }
Console.WriteLine("O vetor está Ordenado");
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) {
 list($valor_1, $valor_2) = array($valor_2, $valor_1);
 }
 
 /* Array de teste */
 $arrToSort = array(1, 4, 7, 3, 8, 9, 10);
 $length = count($arrToSort);
 /* a BOLHA! ;-) */
 for ($i = 0; $i < $length; $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 = 0; $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);
var_dump($items );//Imprimindo Array Atual
BubbleSort( $items );//Ordenando o Array
var_dump($items );//Imprimindo Array Ordenado
?>
Shell script
#! /bin/bash
vetor=( 2 1 3 4 5 )
bubble_sort(){
 aux=0
 for (( a = 0 ; a < ${#vetor[*]} ; a++ ))
 do
 for (( b = 0 ; b < ${#vetor[*]} ; b++ )) 
 do
 [[ ${vetor[$b]} -lt ${vetor[$a]} ]] && { aux=${vetor[$b]} ; vetor[$b]=${vetor[$a]} ; vetor[$a]=$aux ; }
 done
 done
}
bubble_sort
echo "${vetor[*]}"
Lua
function bubbleSort(v)
 --Lembrando que vetores no lua começam no "1" e não no "0"
 for i=#v, 1, -1 do
 for j=1, i-1 do -- Lembrando que se o "passo" do loop for for 1 não precisa coloca-lo
 if(v[j]>v[j+1])then
 v[j],v[j+1] = v[j+1],v[j]
 end
 end
 end
end
Matlab
for(i = 1:n-1)
 for(j = 1:n-i)
 if(x(j) > x(j + 1))
 aux = x(j);
 x(j) = x(j + 1);
 x(j + 1) = aux;
 end
 end
end
R
bubblesort = function(x){
 n = length(x)
 for(i in 1:(n-1)){
 for(j in 1:(n-i)){
 if(x[j] > x[j+1]){
 aux = x[j]
 x[j] = x[j+1]
 x[j+1] = aux
 }
 }
 }
 return(x)
}
ASP
<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
JavaScript
var vetor = [5, 2, 1, 3, 4];
for (var i = 0 ; i < vetor.length; i++)
{
 for (var j = 0; j < i; j++)
 {
 if (vetor[i] < vetor[j])
 {
 var troca = vetor[i];
 vetor[i] = vetor[j];
 vetor[j] = troca;
 }
 }
} 
Visual Basic
Private Sub sbOrdena(aNumbers() As Integer)
 Dim iNumber1 As Integer
 Dim iNumber2 As Integer
 Dim iNumberAux As Integer
 
 For iNumber1 = 0 To UBound(aNumbers)
 For iNumber2 = 0 To UBound(aNumbers) - 1
 If aNumbers(iNumber2) > aNumbers(iNumber2 + 1) Then
 iNumberAux = aNumbers(iNumber2)
 aNumbers(iNumber2) = aNumbers(iNumber2 + 1)
 aNumbers(iNumber2 + 1) = iNumberAux
 End If
 Next iNumber2
 Next iNumber1
End Sub
Fluxograma
Ver também
Ordenação de vector
Quick sort
Heapsort
Merge sort
Selection sort
Pesquisa binária
Ligações externas
C2.com (http://c2.com/cgi/wiki?BubbleSort)
CS (http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html)
Veja também um algoritmo bubble sort oscilante em C (http://leocapetta.blogspot.com/2010/09/bubble-
sort-em-c.html)
Bubble Código de classificação (http://www.algorithm-code.com/wiki/Bubble_sort)
[1] (http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort)
Simulador online do Bublesort (http://wikipedia.artudi.org/Bubble%20Sort.php)
Exemplo de Bubble-Sort com "Dança" (http://www.patternizando.com.br/2011/04/algoritmo-bubble-
sort-demonstrado-com-danca/)
Sou Computeiro (http://soucomputeiro.blogspot.com)
[2] (http://www.dei.isep.ipp.pt/~i960231/ei/bubblesort.htm)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Bubble_sort&oldid=33176234"
Categoria: Algoritmos de ordenação
Navigation menu
Esta página foi modificada pela última vez à(s) 19h02min de 4 de dezembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.