45. 선택정렬

선택정렬이란?

선택정렬은 가장 간단한 정렬 알고리즘 중 하나로, 이 알고리즘은 주어진 리스트에서 최솟값을 선택하여 정렬된 부분과 위치를 교환하는 과정을 반복하여 전체 리스트를 정렬하는 방식이다.

 

동작방식

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

2. 최솟값을 정렬되지 않은 부분의 맨 앞 요소와 교환한다.

3. 정렬된 부분의 크기를 1 증가시킨다.

4. 정렬된 부분의 크기가 전체 리스트의 크기와 같아질 때까지 반복한다.

 

선택정렬은 비교적 간단하지만 효율성은 낮은 편이다.

최선, 평균, 최악의 시간복잡도 모두 O(n^2)이다.

---

#define SWAP(a,b,t) ((t=a), (a=b), (b=t))

void Selection(int User_Data[], int i, int n){
	int j, temp, min;
	
	// 정렬되지 않은 부분에서 가장 작은 값을 찾아 위치를 교환시킨다. 
	for(j=i+1, min=i; j<n; j++)
		if(User_Data[j] < User_Data[min])
			min = j;
	SWAP(User_Data[i], User_Data[min], temp);
}

void Selection_Sort(int User_Data[], int n){
	int i;
	
	// 마지막에는 정렬이 필요 없으므로 n-1번 반복한다. 
	for(i=0;i<n-1;i++)
		Selection(User_Data,i,n);
}