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) |
 | |
| 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 |
O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer um conjunto de elementos 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.
Implementações
[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; }
def bubble_sort(numeros: list[float], verbose: bool = False): """ Ordena uma lista de números de forma ascendente. BigO* = n²-n *Embora a literatura considere a complexidade n². """ n = len(numeros) bigO = 0 if verbose: print(f"BigO* = {n}²-{n} = {n ** 2 - n}") print(f"*Embora a literatura considere a complexidade n².") for i in range(n): for j in range(n - 1): bigO += 1 x = numeros[j] y = numeros[j+1] swap = x > y if verbose: print(f'BigO({bigO}) => {numeros} x={x} y={y} Swap: {swap}') if swap: numeros[j], numeros[j+1] = y, x return numeros array = [9,8,7,6,5,4,3,2,1,0] print(f"Lista desordenada: {array}") print(f"Lista ordenada...: {bubble_sort(array, verbose=True)}") // Loop fn bubble_sort_loop<T>(mut array_to_sort []T, compare fn (a T, b T) bool) { array_to_sort_len := array_to_sort.len for i in 0..array_to_sort_len { for j in i + 1..array_to_sort_len { if compare(array_to_sort[i], array_to_sort[j]) { array_to_sort[i], array_to_sort[j] = array_to_sort[j], array_to_sort[i] /*tmp := array_to_sort[i] array_to_sort[i] = array_to_sort[j] array_to_sort[j] = tmp*/ } } } } fn bubble_sort_loop_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T { mut array_to_sort_clone := array_to_sort.clone() bubble_sort_loop<T>(mut array_to_sort_clone, compare) //return function_clone<T>(bubble_sort_loop, array_to_sort, compare) return array_to_sort_clone } // Recursion fn bubble_sort_recursion<T>(mut array_to_sort []T, compare fn (a T, b T) bool) { array_to_sort_len := array_to_sort.len if array_to_sort_len <= 1 { return } for i in 0..array_to_sort_len - 1 { if compare(array_to_sort[i], array_to_sort[i + 1]) { array_to_sort[i], array_to_sort[i + 1] = array_to_sort[i + 1], array_to_sort[i] /*tmp := array_to_sort[i] array_to_sort[i] = array_to_sort[j] array_to_sort[j] = tmp*/ } } bubble_sort_recursion<T>(mut array_to_sort[0..array_to_sort_len - 1], compare) } fn bubble_sort_recursion_clone<T>(array_to_sort []T, compare fn (a T, b T) bool) []T { mut array_to_sort_clone := array_to_sort.clone() bubble_sort_recursion<T>(mut array_to_sort_clone, compare) return array_to_sort_clone } // Bubble Sort enum LoopRec { loop recursion } fn bubble_sort<T>(mut array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) { match loop_rec { .loop { bubble_sort_loop<T>(mut array_to_sort, compare) } .recursion { bubble_sort_recursion<T>(mut array_to_sort, compare) } } } fn bubble_sort_clone<T>(array_to_sort []T, compare fn (a T, b T) bool, loop_rec LoopRec) []T { return match loop_rec { .loop { bubble_sort_loop_clone<T>(array_to_sort, compare) } .recursion { bubble_sort_recursion_clone<T>(array_to_sort, compare) } } } 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
Ligações externas
[editar | editar código-fonte]| Teoria |  | |
|---|---|---|
| Exchange sorts | ||
| Selection sorts | ||
| Insertion sorts | ||
| Merge sorts | ||
| Outros | ||
| Ordenações ineficientes/humorísticas | ||
