C++의 버블 정렬 알고리즘
이 기사에서는 C++에서 버블 정렬 알고리즘을 구현하는 방법에 대한 몇 가지 방법을 설명합니다.
std::vector컨테이너에 대한 버블 정렬 구현
버블 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 인접한 각 쌍을 비교하는 객체 목록을 반복하며 순서가 지정되지 않은 경우 요소가 교체됩니다. 요소의 유일한 읽기는 비교 표현식을 사용하여 수행되므로 비교 정렬 알고리즘으로 분류됩니다. 다음 예제 코드에서는 일반vector객체에서 작동하도록 버블 정렬을 구현합니다. bubbleSort라는 단일 함수는 전체 정렬 루틴을 정의하기에 충분합니다. 이 함수는 템플릿 화되고벡터를 유일한 인수로 참조합니다.
bubbleSort에는 오름차순으로 정렬 될 때까지vector 요소를 반복하는 두 개의 중첩 된for 루프가 포함됩니다. 외부 for루프의 각 반복은 올바른 위치에 하나의 요소를 저장합니다. 후자의 요소는 벡터의 끝에 저장되며 내부 루프에서 순회되는 벡터 부분에서 가장 큰 요소가됩니다. 구현을 단순화하고 더 읽기 쉽게 만들기 위해std::swap 알고리즘을 사용했습니다.
#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;
}
출력:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
경험적 타이밍 측정으로 버블 정렬 복잡성 분석
버블 정렬은 2 차 실행 시간 클래스에 속합니다. 사실,이 알고리즘의 평균 시간과 최악의 경우 성능은 모두 2 차-O(n2)입니다. 따라서이 방법은 큰 입력 데이터 세트에 대해 완전히 비효율적입니다. 바로 이런 이유로 실제로 사용되지 않습니다. 예를 들어, 입력 벡터 길이를10만큼 늘리면 실행 시간이 대략100배 증가합니다. 그러나 버블 정렬은 입력 벡터의 요소가 한 위치에서만 순서가 맞지 않는 특수한 경우에 매우 효율적일 수 있습니다 (예 :1032547698시퀀스). 후자의 경우 알고리즘 복잡도를 선형으로 만듭니다. 다음 코드 예제는gettimeofday함수를 사용하여 두 개의 다른 벡터에 대한 실행 시간을 측정하고 결과를 콘솔에 출력합니다.
#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;
}
출력:
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