Bubble Sort
버블정렬은 Stable한 정렬로 인접한 두 데이터의 대소관계를 비교해 규칙에 적합한 데이터를 뒤로 보내는 방식으로 정렬을 수행한다
O(N^2)의 시간복잡도와 O(1)의 공간 복잡도를 가지게 되며 코드가 단순해 구현이 간단하다
동작 원리
오름차순 정렬 기준
- 0번째 인덱스와 1번째 인덱스의 데이터를 비교한다
- 0번째 인덱스가 크다면 1번째 인덱스와 스왑한다
- 1번째 인덱스가 크거나 같다면 스왑하지 않는다
- N-1번째 인덱스와 N번째 인덱스까지 비교하게 되면 N번째 인덱스에는 배열의 최대값이 삽입되어 있다
- 다시 1번으로 돌아가 N-1번째 인덱스까지 반복한다
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>
using namespace std;
void BubbleSort(vector<int> &bubbleSortVec){
int MAXSIZE = bubbleSortVec.size();
for(int repeat = 0; repeat < MAXSIZE; ++repeat){
for(int start = 0; start < MAXSIZE-repeat-1; ++start){
if(bubbleSortVec[start] > bubbleSortVec[start+1]) {
bubbleSortVec[start] ^= bubbleSortVec[start+1] ^= bubbleSortVec[start] ^= bubbleSortVec[start+1];
}
}
}
}
int main(){
std::srand ( unsigned ( std::time(0) ) );
vector<int> vec(1000);
iota(begin(vec),end(vec),1);
std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
cout<<"Before Bubble Sorting"<<endl;
for(auto num : vec)
cout<<num<<" ";
BubbleSort(vec);
cout<<"After Bubble Sorting"<<endl;
for(auto num : vec)
cout<<num<<" ";
}
|
같이보기
