Bubble sort

Origem: Wikipédia, a enciclopédia livre.
Bubble sort

Bubble sort animation.gif
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

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.

Implementações[editar | editar código-fonte]

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

C[editar | editar código-fonte]

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[editar | editar código-fonte]

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

Ligações externas[editar | editar código-fonte]