알고리즘 정리에서는 알고리즘에 대해 공부하면서 배운 내용을 정리해보겠다.
먼저 선택 정렬에 대해 알아보겠다.
선택 정렬은 가장 작은 것을 하나 뽑아서 맨 앞에 두고, 남은 것 중에서 또 작은 것을 뽑아서 두번째에 두면서 계속 진행하여 결국 모든 원소들을 정렬하는 방법이다.
코드로 구현해보면
#include <stdio.h>
int main() {
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 (array[j] < min) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = min;
array[index] = temp; // swaping
}
for (i = 0; i < 10; i++) {
printf("#%d %d\n", i, array[i]);
}
return 0;
}
여기서 min의 초기값인 9999는 배열에 들어있는 어떤 수보다 큰 값으로, 상황에 따라 바꿔주면 된다.
결과는
#0 1
#1 2
#2 3
#3 4
#4 5
#5 6
#6 7
#7 8
#8 9
#9 10
으로, 잘 정렬된 것을 볼 수 있다.
선택 정렬의 효율성을 알아보자.
선택 정렬의 시간 복잡도는 O(n^2)로, 매우 비효율적이다.
쉽게 생각하자면 위의 예는 첫번째는 10개를 모두 살펴보고, 두번째에는 맨 앞에 있는 1을 제외한 나머지 9개, 이런 식으로 계속 진행하다보면 10 + 9 + 8 + ... 이렇게 되어 n(n+1)/2를 만족하기 때문에 O(n^2)이다.
다음 시간에는 버블 정렬에 대해 알아보도록 하겠다.
'C++ Programming > 알고리즘 정리' 카테고리의 다른 글
[C++] 큐(Queue) (0) | 2020.05.07 |
---|---|
[C++] 스택(Stack) (0) | 2020.05.07 |
[C++] 퀵 정렬 (Quick Sort) (0) | 2020.05.06 |
[C++] 삽입 정렬(Insertion Sort) (0) | 2020.05.06 |
[C++] 버블 정렬(Bubble Sort) (0) | 2020.05.06 |