[Algorithm] Selection Sort

💡 동작원리

이 글에서는 Selection Sort(선택정렬)에 대해 다뤄보려고 한다. Selection Sort(선택정렬)의 원리는 정렬되지 않은 부분배열에서 가장 큰 값, 혹은 가장 작은 값을 찾고 스왑하여 정렬하는 것이다.

위 그림은 오름차순으로 정렬하는 Selection Sort(선택정렬)의 동작원리 중 첫 단계를 그림으로 표현한 것이다. 시행의 목적은 가장 작은 값을 선택해 제일 앞으로 보내주는 것이다. 그래서 정렬되지 않은 부분배열의 가장 앞 원소를 가장 작은 값이라고 가정하고, 뒤에 값들을 비교하며 가장 앞 원소보다 작은 값이 나오면 그 값의 인덱스를 저장하는 방식으로 계속 반복한다. 배열의 끝까지 탐색했을 때, 제일 처음 시작한 원소와 가장 작은 값의 인덱스가 다르면 스왑해준다. 이 시행을 배열이 정렬 될 때까지 해준다. 이렇게 가장 큰 값, 또는 가장 작은 값을 선택하여 정렬시켜주는 방식이 Selection Sort(선택정렬)이다.

💻 코드

void Selection_Sort(){
	for(int i = 0 ; i < N; i++){
		int temp = i;          
		for(int j = i  + 1; j < N; j++)  {
			if(Arr[j] < Arr[temp]) temp = j;   
		}
		if(i != temp) swap(Arr[i], Arr[temp]);   
	}
}

⏱ 시간복잡도

연산 횟수를 계산해보면, $(N-1) + (N-2) + ... + (1) = N(N-1)/2$ 이므로 시간복잡도는 $O(N^2)$이 된다.

$O(N^2)$