대학교/Algorithm
[정렬] 선택 정렬
SWKo
2020. 1. 28. 19:51
0. 핵심 아이디어
- 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까?
1. 예시
- 1 10 5 8 7 6 4 3 2 9
- 1 2 5 8 7 6 4 3 10 9
- 1 2 3 8 7 6 4 5 10 9
- 1 2 3 4 7 6 8 5 10 9
- 1 2 3 4 5 6 8 7 10 9
- 1 2 3 4 5 6 7 8 10 9
- 1 2 3 4 5 6 7 8 9 10
2. 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
int i, j, min, index, temp;
int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i = 0; i < 10; i++){
min = 9999; //모든 원소보다 큰 값이어야 함
for(j = i; j < 10; j++){
if(min > array[j]){
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
for(i = 0; i < 10; i++){
cout << array[i] << " ";
}
return 0;
}
|
3. 시간복잡도
N * (N+1) / 2 => O(N^2)