[알고리즘] 선택 정렬 (Selection Sort)

1. 선택 정렬(Selection Sort)이란?

전체 데이터들 중에서 기준 위치에 맞는 데이터를 선택하여 자리를 교환하는 방식의 정렬 기법이다.

 

2. 알고리즘

 1) 주어진 리스트 중에 최소값을 찾는다.

 2) 그 값을 맨 앞에 위치한 값과 교체한다.

 3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 4) 위 과정을 (데이터 수 - 1)번 반복

 

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

 

 

3. 선택 정렬 예제

배열에 9, 5, 7, 3, 1이 들어 있다고 가정하고 정렬해 보자.

 

첫번째 : 

최소값 1 검색, 첫번째 자리 값 9와 최소값 1 교환

 

두번째 : 

첫번째 자리 제외한 빨간 리스트에서 최소값 3 탐색, 빨간 리스트의 첫번째 자리 값 5와 최소값 3 교환

 

세번째 :

이전 빨간 리스트에서 첫번째 자리 제외한 최소값 3 탐색, 빨간 리스트의 첫번째 자리 값 7과 최소값 5 교환

 

네번째 : 

같은 방식으로 비교, 변화 없음.

 

4. 선택 정렬 C언어 코드 (for문 구현방식과 재귀호출 구현방식)

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
void iteratorSelectionSort(int* ary, int n);
void recursiveSelectionSort(int* ary, int n);
void init(int* ary, int n), printArray(int* ary, int n);
int  main()
{
	int mArray[10], arySize;
	arySize = sizeof(mArray) / sizeof(mArray[0]);
	srand((unsigned int)time(NULL));

	init(mArray, arySize);
	iteratorSelectionSort(mArray, arySize);
	printArray(mArray, arySize);

	init(mArray, arySize);
	recursiveSelectionSort(mArray, arySize);
	printArray(mArray, arySize);
	getchar();
	return 0;

}

void init(int* ary, int n)
{
	int i;
	for (i = 0; i < n; i++)
		ary[i] = rand() & 20 + 1;

}

void printArray(int* ary, int n)
{
	int i;
	printf("배열 내용 : ");
	for (i = 0; i < n; ++i)
		printf("%4d", ary[i]);
	printf("\n");
}

void iteratorSelectionSort(int* ary, int n)
{
	int i, j, temp, target;
	for (i = 0; i < n - 1; i++) {
		target = i;
		for (j = i + 1; j < n; j++) {
			if (ary[target] > ary[j]) {
				target = j;
			}
		}

		temp = ary[target];
		ary[target] = ary[i];
		ary[i] = temp;
	}


	return;
}

void recursiveSelectionSort(int* ary, int n)
{
	int i, temp, target;

	if (n == 1) {
		return;
	}
	target = 0;
	for (i = 0; i < n; i++) {
		if (ary[target] > ary[i]) {
			target = i;
		}
	}

	temp = ary[target];
	ary[target] = ary[0];
	ary[0] = temp;

	return recursiveSelectionSort(ary+1, n-1);
}

 

5. 선택 정렬 특징

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있습니다.

 

 

참고문헌

선택 정렬 - 위키백과