[알고리즘] 선택정렬 쉽게 생각하기

Selection Sort 선택 정렬은
i기준으로 i의 오른쪽(정렬되지 않은 곳)에서 가장 작은 값을 찾은 뒤에 i랑 바꾸는 것입니다.  arr[i]라는 기준 값을 key나 min에 담는 것은 같지만, 내부적으로 정렬하는 것이면 삽입정렬이됩니다. 그런데 내부는 이미 정렬이 되어있으므로, bubble정렬과 같이 한칸씩 오른쪽로 당겨오게 됩니다.

반면 선택정렬은 기준점 i를 기준으로 정렬되지 않은 모든 값들에 대해서 하나하나씩 검사하면서 최소의 값을 찾습니다.

 

int i, j, min;
for(int i=0; i<n-1; i++){
	min = i;
	for(int j= i+1; j<n; j++){
	if(arr[j] < arr[min]){
	min = j;
	}
    swap(&arr[min], &arr[j]);
}

 

기준점 i에 대해서 본인의 좌표 값을 min = i라고 만든 뒤 다음 칸 j=i+1부터 비교해나가면서 본인보다 작다면 min의 값을 옮긴다. 그리고 옮긴 마지막지점에서 i의 값과 바꿉니다. 마치 꿀벌이 모든 값을 순차적으로 검색한 뒤 최고의 자리를 찾고 나서 벌집 위치를 해당 자리로 옮기는 것과 유사합니다.

 

위와 같은 식이 있따면, 모든 값을 하나하나씩 비교하므로 결국에는 최소 값의 좌표, 인덱스를 알아낼 수 있습니다.

이 아이디어는 나중에 greedy알고리즘에 아이디어로 쓰입니다. 모든 값이 주어져있고, 그 중에 최소값을 min으로 둔 다음에 순차적으로 검색해서 가장 최적의 해를 먼저 해결하는 방법으로 동일 아이디어를 적용하여 해결할 수 있습니다.