1. 선택 정렬(Selection Sort)?
선택 정렬은 가장 작은 것을 찾아서 맨 앞에 놓고, 그 다음 작은 것을 찾아서 그 다음에 놓고 식으로 정렬을 행하는 알고리즘입니다.
2. 예시
5
|
8
|
7
|
1
|
3
|
데이터를 가지고 직접 선택 정렬을 해봅시다.
1. 가장 작은 숫자를 찾는다.
5
|
8
|
7
|
1
|
3
|
2. 찾은 숫자를 맨 앞으로 위치 시킨다. (원래 맨 앞에 있던 숫자와 위치를 바꾼다.)
1
|
8
|
7
|
5
|
3
|
3. 맨 앞의 숫자를 제외하고 1~2를 반복한다.
1
|
8
|
7
|
5
|
3
|
1
|
3
|
7
|
5
|
8
|
1
|
3
|
7
|
5
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
1
|
3
|
5
|
7
|
8
|
3. 특징
선택 정렬은 가장 작은 것을 찾아서 앞에 배치하는 것을 반복하는 알고리즘이므로, 별도의 데이터를 저장하기 위한 배열이 필요하지 않다. (Inplace)
선택 정렬은 정렬과정에서 원소들의 순서가 보존되지 않는다. (Stable하지 않음)
예를 들어, 57713을 정렬할 경우, 두 7의 순서가 보존되지 않는다.
4.시간복잡도
선택 정렬은 가장 작은 숫자를 찾고, 그 숫자를 가장 앞에 위치하도록 하는 것을 반복하는 알고리즘이다.
이 알고리즘의 시간복잡도를 분석하면 다음과 같다. (데이터의 개수는 N)
제일 작은 숫자를 찾기 위해 1~N번째 데이터들을 체크 -> N개의 원소
2번째로 작은 숫자를 찾기 위해 2~N번째 데이터들을 체크 -> N-1개의 원소
3번째로 작은 숫자를 찾기 위해 3~N번째 데이터들을 체크 -> N-2개의 원소
....
N-1번째로 작은 숫자를 찾기 위해 N-1~N번째 데이터들을 체크 -> 2개의 원소
순서를 바꾸는데 걸리는 시간은 O(1), 각각의 데이터들을 체크하는데 걸리는 시간은 O(1)이므로, 총 시간복잡도는 O(1+2+3+...+N-1)이 되어 O(N^2)이 된다.
5. C를 이용한 구현
댓글 없음:
댓글 쓰기