Bubble sort

tipo de algoritmo de ordenação
(Redirecionado de Classificação Bolha)

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.

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

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

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

Referências 

editar

Ligações externas

editar