Bubble sort

Neste artigo, exploraremos o impacto de Bubble sort na sociedade atual. Bubble sort tem sido tema de conversa e debate nos últimos tempos, pois gerou opiniões conflitantes e despertou o interesse de um amplo espectro da população. Ao longo deste artigo analisaremos diferentes aspectos relacionados a Bubble sort, desde sua origem até sua influência em diferentes áreas da vida cotidiana. Da mesma forma, examinaremos diferentes perspectivas e estudos que lançam luz sobre Bubble sort, com o objetivo de fornecer uma visão abrangente deste fenômeno tão relevante hoje.

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
Esta caixa:

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

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 > A then
        // trocar elementos de lugar
        trocar( A, A )
        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 > v) 
            swap(&v, &v);  
    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);
    bubbleSort(v,tam-1);
    for(i=0;i<tam;i++)printf("%d ",v);
    return 0;
}


Python

def bubble_sort(numeros: list, 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
            y = numeros
            swap = x > y

            if verbose:
                print(f'BigO({bigO}) => {numeros} x={x} y={y} Swap: {swap}')

            if swap:
                numeros, numeros = y, x

    return numeros

array = 
print(f"Lista desordenada: {array}")
print(f"Lista ordenada...: {bubble_sort(array, verbose=True)}")

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, array_to_sort) {
        array_to_sort, array_to_sort = array_to_sort, array_to_sort
        /*tmp := array_to_sort
        array_to_sort = array_to_sort
        array_to_sort = 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, array_to_sort) {
      array_to_sort, array_to_sort = array_to_sort, array_to_sort
      /*tmp := array_to_sort
      array_to_sort = array_to_sort
      array_to_sort = tmp*/
    }
  }

  bubble_sort_recursion<T>(mut array_to_sort, 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

Referências 

Ligações externas