Entenda o Algoritmo Bubble Sort

đŸ«§ O Bubble Sort compara cada par de elementos adjacentes e os troca se estiverem fora de ordem.


Entenda o Algoritmo Bubble Sort


Os algoritmos de ordenação possuem diversas utilidades na CiĂȘncia da Computação, dentre elas:

  • Organização e Busca Eficiente;
  • Agilidade para Visualizar e gerar RelatĂłrios;
  • Melhoria do Desempenho
  • E entre outras!

Classificar algoritmos de ordenação por ordem de velocidade Ă© complexo, pois a eficiĂȘncia de cada algoritmo pode variar dependendo da estrutura dos dados de entrada.

No entanto, um dos mais simples Ă© o Bubble Sort.

O Bubble Sort, ou ordenação por flutuação (literalmente “por bolha”), compara elementos adjacentes e os troca se estiverem na ordem errada. Ele repete este processo atĂ© que toda a lista esteja ordenada, Ă© um dos mais fĂĄceis algoritmos para implementar.

Ele possui complexidade O(n^2). O termo “O(n^2)” refere-se Ă  notação Big O(Big O Notation, em inglĂȘs), que Ă© uma forma de descrever a complexidade de tempo de um algoritmo.

A notação Big O fornece uma estimativa do tempo de execução de um algoritmo em função do tamanho da entrada, denotado por “n”.

O(n^2) significa que o tempo de execução do algoritmo aumenta proporcionalmente ao quadrado do tamanho da entrada. Em outras palavras, se o tamanho da entrada (n) dobrar, o tempo de execução serå aproximadamente quatro vezes maior.

O Bubble Sort compara cada par de elementos adjacentes e os troca se estiverem fora de ordem. Isso é feito repetidamente para todos os elementos na lista, resultando em muitas comparaçÔes e trocas.

  • No primeiro passe, ele faz (n-1) comparaçÔes.
  • No segundo passe, faz (n-2) comparaçÔes, e assim por diante.
  • No total, o nĂșmero de comparaçÔes Ă© aproximadamente (n-1) + (n-2) + ... + 1 = n(n-1)/2.

    Isso se traduz em uma complexidade de tempo de O(n^2), indicando que o tempo de execução cresce quadraticamente com o aumento do tamanho da entrada.

A notação Big O Ă© Ăștil porque permite comparar a eficiĂȘncia de diferentes algoritmos sem se preocupar com detalhes especĂ­ficos da implementação ou do hardware. Outros exemplos comuns de complexidade incluem:

  • O(1): Tempo constante, independente do tamanho da entrada.
  • O(log n): Tempo logarĂ­tmico, cresce lentamente em relação ao tamanho da entrada.
  • O(n): Tempo linear, cresce diretamente proporcional ao tamanho da entrada.
  • O(n log n): Tempo linearĂ­tmico, comum em algoritmos de ordenação eficientes como Merge Sort e Quick Sort.
  • O(n^3): Tempo cĂșbico, cresce proporcionalmente ao cubo do tamanho da entrada.

Essas expressÔes ajudam a entender como a performance de um algoritmo escala à medida que o tamanho dos dados de entrada aumenta.


Assista ao VĂ­deo


CĂłdigo criado no vĂ­deo

#include <iostream>
#include <vector>

auto bubble_sort = [](std::vector<int>& v){
  for (size_t i {}; i < v.size() - 1; ++i){
    for (size_t j {}; j < v.size() - (i + 1); ++j){
      if(v[j] > v[j + 1]){
        std::swap(v[j], v[j + 1]);
      } 
    }
  }
};

int main(){
  std::vector<int> v {11, 2, 13, 17, 12, 8, 4};
  bubble_sort(v);
  for(auto &var : v){
    std::cout << var << ' ';
  }
  std::cout.put('\n');
  return EXIT_SUCCESS;
}

programacao desenvolvimento cpp


Compartilhe


Nosso canal no Youtube

Inscreva-se


Marcos Oliveira

Marcos Oliveira

Desenvolvedor de software
https://github.com/terroo


Crie Aplicativos GrĂĄficos para Linux e Windows com C++

Aprenda C++ Moderno e crie Games, Programas CLI, GUI e TUI de forma fĂĄcil.

Saiba Mais

Receba as novidades no seu e-mail!

ApĂłs cadastro e confirmação do e-mail, enviaremos semanalmente resumos e tambĂ©m sempre que houver novidades por aqui para que vocĂȘ mantenha-se atualizado!