알고리즘/실전알고리즘강좌(동빈나)
정렬(sorting) - 선택정렬(selection sort), 버블정렬(bubble sort), 삽입정렬(insertion sort), 퀵정렬(quick sort)
밀루루
2021. 12. 28. 22:12
선택정렬
선택정렬은 말 그대로 '선택'하여 진행하는 정렬이다.
선택정렬의 알고리즘은, 먼저 정렬할 배열을 순회하면서 가장 작은 숫자를 선택하고, 제일 앞에 있는 숫자와 순서를 바꾸는 것으로, 이와 같은 것을 배열의 크기 n 만큼 반복한다.
이해하기 쉽게 예를 들면 아래와 같다.

아래는 내가 짠 선택정렬의 코드이다. 강의에서는 가장 작은 수와 인덱스를 모두 저장하였지만 나는 인덱스만 저장하는 식으로 코드를 짰다는 것에서의 차이가 있었다.
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
|
#include <stdio.h>
int main() {
int sort[10] = { 1,3,5,8,9,6,2,4,10,7 };
int small=0, index=0, temp, i;
for (index; index < 10; index++) {
//find small
small = index;
for (i = index; i < 10; i++) {
if (sort[i] < sort[small])
small = i;
}
//swap small one and first one
temp = sort[index];
sort[index] = sort[small];
sort[small] = temp;
}
//print sort
for (int i = 0;i < 10;i++) {
printf("%d ", sort[i]);
}
return 0;
}
|
cs |
이러한 선택정렬의 한계에 대해서 살펴보면,
배열의 크기가 10(n=10)이라고 할 때, 10+9+8+...+1 만큼 반복하게 되는데, 이는 등차 수열로 10(10+2)/2 만큼 반복하게 된다. 즉, 배열의 크기가 n일때, n(n+1)/2 만큼 반복하게 되므로, 선택정렬의 시간복잡도는 O(n*n)이다.
버블정렬

삽입정렬
