[Algorithm] 선택 정렬 (Selection Sort)

선택 정렬은 차례대로 하나의 값을 선택한 후 다른 값과 비교하여 정렬하는 정렬 알고리즘입니다.

 

다음과 같은 과정으로 이루어집니다.

1. 기준 원소 선택
2. 해당 원소 이후의 원소 값들과 비교
3. 기준 원소가 마지막 원소까지 도달할 때 까지 반복

[그림 1] 예제 배열

[그림 1]과 같은 배열이 있다고 했을 때, 오름차순으로 선택정렬을 해 보겠습니다.

 

1. 기준 원소 선택

[그림 2] 기준 원소 선택

기준 원소 선택은 차례대로 이루어집니다. 기준 원소는 i라고 하겠습니다.

우선 첫 번째 원소를 기준으로 잡고, 비교가 완료되면 두 번째, 세 번째...

 

2. 해당 원소 이후의 원소 값들과 비교

[그림 3] 해당 원소 이후의 값들과 비교

i 이후의 원소들을 비교합니다. [그림 3]에서 j 표시된 부분 하나하나 비교해주면 됩니다.

i = 3일 경우에는 i보다 작은 j가 없으므로 넘어가겠습니다.

 

3. 기준 원소가 마지막 원소까지 도달할 때 까지 반복

[그림 4] i 재설정 후 j와 비교

i를 두 번째 원소로 놓고 다시 비교합니다. 앞 쪽은 정렬이 완료되었으니 뒤쪽만 비교합니다.

[그림 4]에서 확인했을 때, 최솟값은 5이므로 해당 원소와 swap합니다.

[그림 5] i와 최솟값 swap

[그림 5]에서 swap됨을 확인할 수 있습니다.

 

이런 식으로 i가 마지막에 도달할 때 까지 반복하면 됩니다.

(원소 개수가 n인 경우, i가 n-1까지 도달하면 됩니다. i가 맨 끝에 도달하면 비교할 게 없어서 의미가 없습니다.)

 

---

C++로 작성된 선택 정렬 알고리즘 코드입니다.

#include <iostream>
#define SIZE 7
using namespace std;

int main() {
	int arr[7] = {3, 10, 5, 45, 8, 6, 12};   // 배열 길이, 배열 값 저장 변수 
	
	cout << "정렬 전 배열 :" << ' ';
	for(int i = 0; i < SIZE; i++) {
		cout << arr[i] << ' ';
	}
	
	/* 선택 정렬 */
	for(int i = 0; i < SIZE; i++) {
		int idx = i;   // 현재 index 저장 
		for(int j = i; j < SIZE; j++) {
			if(arr[idx] > arr[j]) idx = j;  // 현재 선택된 원소(arr[j])가 기준 값(arr[idx])보다 작으면 index 새로 저장 
		}
		/* 최종적으로 작은 값의 index를 이용해 원소 swap */
		int temp = arr[idx];
		arr[idx] = arr[i];
		arr[i] = temp;
	}
	
	cout << '\n' << "정렬 후 배열 :" << ' ';
	for(int i = 0; i < SIZE; i++) {
		cout << arr[i] << ' ';
	}
}

[그림 6] 실행 결과

정렬이 되었음을 확인할 수 있습니다.