[알고리즘] 선택 정렬(選擇整列, Selection Sort)

 

 

 

 

알고리즘 개요 및 소개

선택 정렬 애니메이션

선택 정렬은 제자리 정렬 알고리즘의 하나로 다음과 같은 순서로 이루어진다.

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

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

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

 

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

선택 정렬은 대략 N*(N+1)/2번가량의 연산을 수행하기 때문에 시간 복잡도는 O(N^2)이다.

 

시간 복잡도	O(N^2)
장점	메모리가 제한적인 경우에 성능의 이점이 있다.
단점	느린 속도, 많은 연산량

 

소스코드

#include

constexpr int MAX_LIST = 10;

/*
Select Sort 알고리즘의 핵심은 가장 작은숫자를 선택해서 앞으로 보내자
*/

int main() {
	int list[MAX_LIST] = { 10,1,3,2,8,5,9,4,6,7 };
	int temp, index, min;
	for (int i = 0; i < MAX_LIST; ++i) {
		min = 0x0FFFFFFF;
		for (int j = i; j < MAX_LIST; ++j) {

			if (list[j] < min) {
				min = list[j];
				index = j;
			}

		}
		temp = list[i];
		list[i] = list[index];
		list[index] = temp;
	}

	for (auto i : list) {
		std::cout << i << " ";
	}

	system("pause");
}

 

후기

알고리즘의 기초라고 할 수 있는 정렬 중에 선택 정렬을 구현해보았다. 

온라인 코딩문제를 풀어보면서 탐색 알고리즘 등 여러 알고리즘의 중요성을 깨달았기 때문에 당분간은 알고리즘 공부를 먼저 하고 온라인 코딩 문제를 푸는 방식으로 가야 할 거 같다.

 

 

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/선택_정렬

Blog: https://blog.naver.com/ndb796/221226800661