Bubble sort

Bubble sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$O(n^{2})$
complexidade caso médio	$O(n^{2})$
complexidade melhor caso	$O(n)$
complexidade de espaços pior caso	$O(1)$ auxiliar
Algoritmos

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 $n$ operações relevantes, onde $n$ representa o número de elementos do vector. No pior caso, são feitas $n^{2}$ 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

Pseudocódigo

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

C

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;
}

V

// 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

• Algoritmo de ordenação
• Quick sort
• Heapsort
• Merge sort
• Selection sort
• Pesquisa binária

Referências 

• 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

• Implementação do algoritmo em várias linguagens de programação
• C2.com