Selection Sort(선택 정렬)

선택정렬은 제자리 정렬 알고리즘에 속하고, 주어진 리스트나 배열을 정렬하는 방법 중 하나다.

1. Selection Sort(선택 정렬) 문제

예제를 통해서 선택 정렬을 한 번 알아보자

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하라.

1 10 5 8 7 6 4 3 2 9

2. Selection Sort(선택 정렬) 풀이

선택정렬로 문제를 해결해보자

배열의 숫자 중 가장 작은 것을 선택해서 제일 앞으로 보낸다

첫번째 숫자에 가장 작은 숫자가 오도록 한 뒤,

두번쨰 숫자에 올 숫자를 탐색해 나간다

이를 계속 반복해나가면 다음과 같이 표현된다

1. 1 10 5 8 7 6 4 3 2 9
2. 1 2 5 8 7 6 4 3 10 9
3. 1 2 3 8 7 6 4 5 10 9
4. 1 2 3 4 7 6 8 5 10 9
5. 1 2 3 4 5 6 8 7 10 9
6. 1 2 3 4 5 6 7 8 10 9
7. 1 2 3 4 5 6 7 8 9 10

// 다음의 배열을 오름차순으로 정렬하시오
const arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];

// 최솟값을 담아줄 변수 min
let min;

// 최솟값의 인덱스를 저장할 변수 min_index
let min_index;

// 현재값을 저장해 둘 변수 temp
let temp;

for (let i = 0; i < arr.length; i++) {
	// 단, 최솟값을 담아줄 변수이기 때문에 요소들보다 큰 숫자를 넣어주어 비교할 첫 번째 요소가 들어갈 수 있도록 한다
	min = 9999;
	for (let j = i; j < 10; j++) {
		if (min > arr[j]) {
			min = arr[j];
			// 최솟값으로 설정된 인덱스를 기억한다
			min_index = j;
		}
	}
	// 인덱스의 값을 temp변수에 담는다
	temp = arr[i];
	// 최솟값을 해당 인덱스에 넣어준다
	arr[i] = arr[min_index];
	// 최솟값의 자리에 현재의 값을 넣어줌으로 자리를 스왑한다
	arr[min_index] = temp;
}

console.log(arr);

3. Selection Sort(선택 정렬)의 효율성

위의 예제에서는 10 + 9 + ... + 1 까지 총 55회의 연산이 필요하다

이를 수식으로 표현하면, n(n + 1)/2 번의 비교연산을 해야한다

따라서 O(n^2)의 수행시간을 가진다

참고자료

동빈나 유튜브
https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz