Algoritmo de classificação de bolhas em C++
-
Implementar classificação por bolha para recipiente
std::vector
- Analise a complexidade da classificação por bolha com medições de tempo empíricas
![Algoritmo de classificação de bolhas em C++](/img/Cpp/feature-image---bubble-sort-in-cpp.webp)
Este artigo explicará vários métodos de como implementar o algoritmo de classificação de bolhas em C++.
Implementar classificação por bolha para recipiente std::vector
A classificação por bolha é um dos algoritmos de classificação mais simples. Ele itera através da lista de objetos comparando cada par adjacente e, se eles não forem ordenados, os elementos serão trocados. É classificado como um algoritmo de ordenação por comparação, pois a única leitura dos elementos é feita através da expressão de comparação. No código de exemplo a seguir, implementamos a classificação por bolha para funcionar em objetos vector
genéricos. Uma única função chamada bubbleSort
é suficiente para definir toda a rotina de classificação. A função é modelada e leva uma referência a um vector
como o único argumento.
bubbleSort
inclui dois loops for
aninhados para iterar sobre os elementos vetor
até que sejam classificados em ordem crescente. Observe que cada iteração do loop externo for
armazena um elemento em um lugar correto. O último elemento é armazenado no final do vetor e passa a ser o maior elemento na parte do vetor que é percorrida no loop interno. Observe que utilizamos o algoritmo std::swap
para simplificar a implementação e torná-la mais legível.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
void bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
bubbleSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
Resultado:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
Analise a complexidade da classificação por bolha com medições de tempo empíricas
A classificação por bolha pertence a uma classe quadrática de tempo de execução. Na verdade, o tempo médio e o desempenho de pior caso desse algoritmo são quadráticos - O(n2). Portanto, esse método se torna totalmente ineficiente para grandes conjuntos de dados de entrada. Não é usado praticamente por esse motivo. Por exemplo, se aumentarmos o comprimento do vetor de entrada em 10
, o tempo de execução aumentará aproximadamente por um fator de 100
. Observe, porém, que a classificação por bolha pode ser bastante eficiente para um caso especial quando os elementos no vetor de entrada estão fora de ordem em apenas um lugar (por exemplo, sequência 1032547698
). O último caso tornaria a complexidade do algoritmo linear. O exemplo de código a seguir mede o tempo de execução para dois vetores diferentes usando a função gettimeofday
e envia os resultados para o console.
#include <sys/time.h>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void bubbleSort(vector<T> &vec) {
for (size_t i = 0; i < vec.size() - 1; ++i) {
for (size_t j = 0; j < vec.size() - i - 1; ++j) {
if (vec.at(j) > vec.at(j + 1)) std::swap(vec.at(j), vec.at(j + 1));
}
}
}
float time_diff(struct timeval *start, struct timeval *end) {
return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}
int main() {
struct timeval start {};
struct timeval end {};
vector<int> vec3(100, 10);
vector<int> vec4(1000, 10);
gettimeofday(&start, nullptr);
bubbleSort(vec3);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec3.size(),
time_diff(&start, &end));
gettimeofday(&start, nullptr);
bubbleSort(vec4);
gettimeofday(&end, nullptr);
printf("bubbleSort %zu elements: %0.8f sec\n", vec4.size(),
time_diff(&start, &end));
return EXIT_SUCCESS;
}
Resultado:
bubbleSort 100 elements: 0.00002500 sec
bubbleSort 1000 elements: 0.00184900 sec
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook