Bubble sort – Wikipédia  a enciclopédia livre
15 pág.

Bubble sort – Wikipédia a enciclopédia livre


DisciplinaAlgoritmos14.811 materiais172.858 seguidores
Pré-visualização3 páginas
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 &quot;houve troca&quot;.
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 &quot;n²&quot;, 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(&quot;Digite o valor: &quot;);
 scanf(&quot;%d&quot;,&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(&quot;%d&quot;,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 &quot;do while&quot;.
void swapbubble( int v[], int i)
{
 
int aux=0; 
 
 aux=v[i];
 v[i] = v[i+1];
 v[i+1] = aux;
 
}
 
 void