선택 정렬
선택 정렬 애니메이션 | |
분류 | 정렬 알고리즘 |
---|---|
자료 구조 | 배열 |
최악 시간복잡도 | 비교, 교환 |
최선 시간복잡도 | 비교, 교환 |
평균 시간복잡도 | 비교, 교환 |
공간복잡도 | 예비 |
선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
예제
[편집]패스 | 테이블 | 최솟값 |
---|---|---|
0 | [9,1,6,8,4,3,2,0] | 0 |
1 | [0,1,6,8,4,3,2,9] | 1 |
2 | [0,1,6,8,4,3,2,9] | 2 |
3 | [0,1,2,8,4,3,6,9] | 3 |
4 | [0,1,2,3,4,8,6,9] | 4 |
5 | [0,1,2,3,4,8,6,9] | 6 |
6 | [0,1,2,3,4,6,8,9] | 8 |
의사 코드
[편집]for i = 0 to n: a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자. a[i]와 a[j]의 값을 서로 맞바꾼다.
복잡도
[편집]최선, 평균, 최악의 경우일 때에 선택 정렬에 소요되는 비교의 횟수를 라고 했을 때, 이를 수식으로 나타내면 다음과 같다.
수식에서 은 테이블(또는 리스트)의 자료 수를 나타내며, 는 평균, 는 최대, 는 최소를 나타낸다.
다른 정렬 알고리즘과의 비교
[편집]버블 정렬(bubble sort) : 시간 복잡도 Θ ( n 2 )인 정렬 알고리즘 중에서 선택 정렬은 버블 정렬보다 항상 우수하다.
삽입 정렬(insertion sort) : 삽입 정렬은 k번째 반복 이후, 첫번째 k 요소가 정렬된 순서로 온다는 점에서 유사하다. 하지만 선택 정렬은 k+1 번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입 정렬은 k+1 번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 훨씬 효율적으로 실행된다는 차이가 있다.
합병 정렬(merge sort) : 선택 정렬은 합병 정렬과 같은 분할 정복 알고리즘을 사용하지만 일반적으로 큰 배열보다 작은 배열(요소 10~20개 미만)에서 더 빠르다. 따라서 충분히 작은 하위 목록에만 삽입 정렬 혹은 선택 정렬을 이용해서 최적화하는 것이 좋다.
다양한 개선 방법
[편집]이중 선택 정렬: 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다.
탐색을 응용하여 개선: 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법이다. 즉, 만약 최솟값을 찾았는데 그 값과 같은 값이 있다면 다음 번 탐색 때 최솟값으로 탐색될 것이기에 이 값도 탐색된 것으로 보고 미리 정렬한다. 같은 값이 많을수록 유용하게 된다.[1]
소스 코드
[편집]Java
[편집]void selectionSort(int[] list) {
int indexMin, temp;
for (int i = 0; i < list.length - 1; i++) {
indexMin = i;
for (int j = i + 1; j < list.length; j++) {
if (list[j] < list[indexMin]) {
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
void selectionSort(int *list, const int n)
{
int i, j, indexMin, temp;
for (i = 0; i < n - 1; i++)
{
indexMin = i;
for (j = i + 1; j < n; j++)
{
if (list[j] < list[indexMin])
{
indexMin = j;
}
}
temp = list[indexMin];
list[indexMin] = list[i];
list[i] = temp;
}
}
let rec ssort = function
| [] -> []
| h::t -> (ssort (etcList (findMax h t) (h::t))) @ [(findMax h t)]
and findMax a = function
| [] -> a
| h::t -> if a>h then (findMax a t) else (findMax h t)
and etcList a = function
| [] -> []
| h::t -> if h=a then t else h :: (etcList a t);;
def selectionSort(x):
length = len(x)
for i in range(length-1):
indexMin = i
for j in range(i+1, length):
if x[indexMin] > x[j]:
indexMin = j
x[i], x[indexMin] = x[indexMin], x[i]
return x
참고 및 관련 문헌
[편집]- Ellis Horowitz, Sartaj Sahni, Dinesh Mehta: Fundamentals of Data structures in C++, Computer science press.
- ↑ 박정식 (2021/06). “탐색을 응용한 선택 정렬의 개선 방법 제안”. 2021년 8월 7일에 확인함.
같이 보기
[편집]이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |