[Sorting 02] Selection Sort의 개념 및 구현

들어가며

---

일기를 쓰는 것과 블로그 포스팅을 하는 것은 정말 꾸준히 하기 힘든 것 같다.

공대생은, 특히나 컴공생은 고학년이 될 수록 한국어가 어려워지는 신기한 현상을 겪게 되기 마련이고

따라서 뭔가를 말로 설명하거나 글로 적어내는 것은 더더욱 어려워지는 거 같다.

 

잘 아는 것과 잘 설명하는 것, 글로 잘 풀어내는 것 전부 참으로 어려운 일이지만

많이 해보다보면 늘겠지 싶은 심정으로 오늘도 블로그 포스팅을 해본다.

 

오늘은 sorting 2번째 포스팅인데

sorting 중에서 가장 쉬운 편에 속하는 알고리즘인 'selection sort'에 대해 소개 하려고 한다.

개념 및 특징

---

• 제자리 정렬이다.
• 최악 시간 복잡도: O(N²)
• 최선 시간 복잡도: O(N²)
• 평균 시간 복잡도: O(N²)

알고리즘

---

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 리스트의 맨 앞의 값과 교환한다.
3. 맨 처음 위치를 제외한 나머지 리스트로 1, 2 과정을 반복한다.

소스코드(C++)

---

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

void selection_sort(vector<int>& vc) 
{
	for(int i=0;i<vc.size();++i) {
		int min = vc[i];
		int min_ind = i;
		for(int j=i+1;j<vc.size();++j) {
			if(vc[j] < min) {
				min = vc[j];
				min_ind = j;
			}
		}
		int tmp = vc[i];
		vc[i] = vc[min_ind];
		vc[min_ind] = tmp;
	}
}

int main(void)
{
	int arr[] = {1, 5, 2, 6, 3, 7, 13, 9};
	vector<int> vc(arr,arr+sizeof(arr)/sizeof(arr[0]));
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	
	selection_sort(vc);
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;	
	return 0;
}

관련문제

---

• 백준 2750번: 수 정렬하기(https://www.acmicpc.net/problem/2750)
• 백준 1181번: 단어 정렬(https://www.acmicpc.net/problem/1181)