Selection Sort
삽입정렬은 UnStable한 정렬로 0번째 인덱스부터 시작해 N번째 인덱스까지 순회하며 최소값을 찾아 스왑한다
O(N^2)의 시간복잡도와 O(1)의 공간 복잡도를 가지게 되며 코드가 단순해 구현이 간단하다
동작 원리
오름차순 정렬 기준
- 0번째 인덱스를 기준으로 삼는다
- 1번째 인덱스부터 N번째 인덱스까지 순회하며 최소값을 탐색한다
- 탐색한 최소값이 0번째 인덱스보다 작다면 스왑한다
- 탐색한 최소값이 0번째 인덱스보다 작지 않다면 스왑하지 않는다
- 다시 1번으로 돌아가 N-1번째 인덱스까지 반복한다
UnStable Sort 예시
배열 : 5[1], 4, 5[2], 3, 2
1회 반복 : 2, 4, 5[2], 3, 5[1]
2회 반복 : 2, 3, 5[2], 4, 5[1]
3회 반복 : 2, 3, 4, 5[2], 5[1]
4회 반복 : 2, 3, 4, 5[2], 5[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
36
37
38
39
40
41
42
| #include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>
using namespace std;
void SelectionSort(vector<int> &selectionSortvec){
int MAXSIZE = selectionSortvec.size();
for(int start = 0; start < MAXSIZE-1; start++){
int min_element_index = start;
for(int find = start+1; find < MAXSIZE; find++){
if(selectionSortvec[min_element_index] > selectionSortvec[find]) {
min_element_index = find;
}
}
if(min_element_index!=start){
selectionSortvec[start] ^= selectionSortvec[min_element_index] ^= selectionSortvec[start] ^= selectionSortvec[min_element_index];
}
}
}
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 Selection Sorting"<<endl;
for(auto it : vec)
cout<<it<<" ";
cout<<endl;
SelectionSort(vec);
cout<<"After Selection Sorting"<<endl;
for(auto it : vec)
cout<<it<<" ";
return 0;
}
|
같이보기
