Bubble sort
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Maio de 2017) |
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, e a cada passagem fazer 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 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.
Pseudocódigo[editar | editar código-fonte]
Este algoritmo percorre a lista de itens ordenáveis do início ao fim, verificando a ordem dos elementos dois a dois, e trocando-os de lugar se necessário. Percorre-se a lista até que nenhum elemento tenha sido trocado de lugar na passagem anterior.
procedure bubbleSort( A : lista de itens ordenaveis ) defined as: do trocado := false for each i in 0 to length( A ) - 2 do: // verificar se os elementos estão na ordem certa if A[ i ] > A[ i + 1 ] then // trocar elementos de lugar trocar( A[ i ], A[ i + 1 ] ) trocado := true end if end for // enquanto houver elementos sendo reordenados. while trocado end procedure
Uma versão em C, recursiva :
Entra: tamanho do vetor a ser organizado e vetor de números.
Saida: vetor organizado.
#include<stdio.h>
#include<stdlib.h>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
void bubbleSort(int *v, int n){
if (n < 1)return;
for (int i=0; i<n; i++)
if (v[i] > v[i+1])
swap(&v[i], &v[i+1]);
bubbleSort(v, n-1);
}
int main(){
int tam,i,*v;
scanf("%d",&tam);
v=(int*)malloc(tam*sizeof(int));
for(i=0;i<tam;i++)scanf("%d",&v[i]);
bubbleSort(v,tam-1);
for(i=0;i<tam;i++)printf("%d ",v[i]);
return 0;
}
Ver também[editar | editar código-fonte]
Referências [editar | editar código-fonte]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 2ed. MIT Press e McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.40.
- Sorting in the Presence of Branch Prediction and Caches
- Fundamentals of Data Structures by Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed ISBN 81-7371-605-6