2024.09.09

[알고리즘] Selection Sort

1. Selection sort

Selection sort(선택 정렬)는 배열에서 가장 작은(또는 가장 큰) 요소를 찾아서 순서대로 정렬해 나가는 단순한 정렬 알고리즘이다. 배열을 처리할 때, 정렬되지 않은 부분에서 최소값을 찾아 정렬된 부분의 끝에 위치시킴으로써 정렬을 확장해 나간다.

이 알고리즘에서는 두 개의 주요 루프가 존재한다.

• 첫 번째 루프는 배열의 모든 요소를 차례로 선택하는 루프로, 인덱스 0부터 배열의 끝(n-1)까지 반복된다.
• 두 번째 루프는 현재 선택된 인덱스부터 배열의 끝까지 탐색하여 최소값의 인덱스를 찾는 과정이다.

2. 구현 분석

void selectionSort(int *arr, int N) {
	for (int i = 0; i < N - 1; i++) { // 루프_1
		int minIndex = i;
		for (int j = i + 1; j < N; j++) { // 루프_2
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		swap(arr[i], arr[minIndex]);
	}
}

2-1. 루프 [1]

for (int i = 0; i < N - 1; i++)

이 부분은 배열의 첫 번째 요소부터 마지막에서 두 번째 요소까지 순차적으로 선택하는 루프이다. 각 반복에서 현재 위치 i부터 배열의 끝까지 중에서 최소값을 찾아 현재 위치에 놓는다. 이때, 마지막 요소는 비교 대상이 되지만, 마지막에는 이미 모든 요소가 정렬되었기 때문에 i는 N - 2까지만 반복하면 된다. 하지만 코드에서는 i < N - 1로 되어 있어 마지막에서 두 번째 요소까지 선택한다.

2-2. 루프 [2]

	for (int j = i + 1; j < N; j++) {
		if (arr[j] < arr[minIndex]) {
			minIndex = j;
		}
	}

이 부분은 현재 선택된 위치 i부터 배열의 끝까지 탐색하여 최소값의 인덱스를 찾는 루프이다. 변수 minIndex는 현재까지 발견한 최소값의 인덱스를 저장하며, 처음에는 i로 초기화된다.

• for (int j = i + 1; j < N; j++): j는 현재 선택된 위치 i의 다음 인덱스부터 시작하여 배열의 끝까지 반복한다. 이를 통해 i 이후의 모든 요소를 비교 대상으로 삼는다.

• if (arr[j] < arr[minIndex]): 현재 탐색 중인 요소 arr[j]가 현재까지의 최소값 arr[minIndex]보다 작으면, minIndex를 j로 업데이트한다. 이 과정을 통해 가장 작은 요소의 인덱스를 찾는다.

• swap(arr[i], arr[minIndex]);: 내부 루프가 끝난 후, 현재 위치 i에 최소값을 가진 요소를 배치하기 위해 arr[i]와 arr[minIndex]를 교환한다. 만약 minIndex가 i와 같다면 이미 올바른 위치에 있으므로 교환은 의미가 없다.

3. 정확성 분석

Selection sort는 배열에서 가장 작은 요소를 선택하여 정렬되지 않은 부분의 첫 번째 위치에 놓는 과정을 반복함으로써 전체 배열을 정렬한다. 이제 귀납법을 통해 Selection sort 알고리즘이 항상 입력된 배열을 올바르게 정렬하는지 그 정확성을 증명해보자.

3-1. 명제 설정

명제 P(i): 반복문이 i번째 반복 후에 배열의 앞부분 A[0…i]은 정렬되어 있고, 이 요소들은 원래 배열의 가장 작은 (i + 1)개의 요소들이다.

3-2. 귀납적 증명의 구성 요소

귀납법은 다음 네 가지 단계로 이루어진다.

1. 기저 사례(Base Case): P(0)이 참임을 보인다.
2. 귀납 가정(Inductive Hypothesis): 임의의 자연수 k에 대해 P(k-1)가 참이라고 가정한다.
3. 귀납 단계(Inductive Step): P(k-1)가 참일 때 P(k)도 참임을 보인다.
4. 종료성(Termination): 알고리즘이 유한한 단계 내에 종료함을 보인다.

3-3. 귀납적 증명

기저 사례

• P(0)이 참임을 보이자.

첫 번째 반복에서 i = 0이다. 내부 루프를 통해 배열 A[0…N-1]에서 가장 작은 요소를 찾아 A[0]과 교환한다. 따라서 A[0]에는 배열 전체에서 가장 작은 값이 저장된다. 그러므로 P(0)은 참이다.

귀납 가정

• P(k-1)가 참이라고 가정하자.

즉, 배열의 앞부분 A[0…k-1]은 정렬되어 있고, 이 요소들은 원래 배열의 가장 작은 k개의 요소들이다.

귀납 단계

• P(k-1)가 참일 때, P(k)도 참임을 보이자.

반복문의 k번째 반복에서 i = k이다. 내부 루프를 통해 A[k…N-1]에서 최소값을 찾아 A[k]와 교환한다. 귀납 가정에 의해 A[0…k-1]은 정렬되어 있고, 배열에서 가장 작은 k개의 요소들이다. 새로운 최소값은 배열에서 (k+1)번째로 작은 값이며, 이를 A[k]에 위치시킴으로써 A[0…k]는 정렬되고, 배열의 가장 작은 (k+1)개의 요소들을 포함하게 된다. 따라서 P(k)는 참이다.

종료성

• 알고리즘이 유한한 단계 내에 종료함을 보이자.

외부 루프는 i = 0부터 i = N - 2까지 총 N - 1회 실행된다. 각 반복마다 내부 루프는 유한한 횟수 내에 종료된다. 따라서 알고리즘은 유한한 단계 내에 반드시 종료한다.

결론

• P(0)이 참이고, P(k-1) ⇒ P(k)가 참이므로, 수학적 귀납법에 의해 모든 자연수 k에 대해 P(k)가 참이다.
• 따라서 알고리즘이 종료된 후 배열 A[0…N-1]은 정렬되어 있다.
• 또한 알고리즘이 유한한 단계 내에 종료하므로, 알고리즘은 정확하게 동작한다.

4. 효율성 분석

4-1. Best Case

선택 정렬의 경우, 입력 배열의 상태와 관계없이 항상 동일한 비교 횟수를 수행한다. 따라서 Best Case와 Worst Case의 시간 복잡도가 동일하다.

void selectionSort(int *arr, int N) {
	for (int i = 0; i < N - 1; i++) {			// 1. (N - 1) Times
		int minIndex = i;						// 2. (N - 1) Times
		for (int j = i + 1; j < N; j++) {		// 3. 1/2 * (N - 1)(N) Times
			if (arr[j] < arr[minIndex]) {		// 4. 1/2 * (N - 1)(N) Times
				minIndex = j;					// 5. 최대 (N - 1) Times
			}
		}
		swap(arr[i], arr[minIndex]);			// 6. (N - 1) Times
	}
}

1. for (int i = 0; i < N - 1; i++)

   • (N - 1) 번 실행된다.

2. int minIndex = i;

   • (N - 1) 번 실행된다.

3. for (int j = i + 1; j < N; j++)

   • 내부 루프의 총 실행 횟수는 다음과 같다:
     • i = 0일 때, j는 1부터 N - 1까지 ⇒ (N - 1) 번
     • i = 1일 때, j는 2부터 N - 1까지 ⇒ (N - 2) 번
     • …
     • 총 합은 $\frac{N(N - 1)}{2}$ 번 실행된다.

4. if (arr[j] < arr[minIndex])

   • 내부 루프와 동일하게 $\frac{N(N - 1)}{2}$ 번 실행된다.

5. minIndex = j;

   • 배열이 이미 정렬된 경우에는 조건이 항상 거짓이므로 이 부분은 실행되지 않는다.
   • 하지만 Best Case에서도 비교 횟수는 동일하므로 시간 복잡도에 영향이 없다.

6. swap(arr[i], arr[minIndex]);

   • (N - 1) 번 실행된다.
   • Best Case에서는 minIndex가 항상 i와 같으므로 교환이 필요 없지만, 코드상으로는 교환 함수가 호출된다.

따라서 선택 정렬의 Best Case 시간 복잡도는 다음과 같다.

$$ \Omega\left(\frac{N(N - 1)}{2}\right) \approx O(N^2) $$

4-2. Worst Case

선택 정렬은 입력 배열의 상태와 관계없이 항상 동일한 비교 횟수를 수행하므로, Worst Case의 시간 복잡도도 Best Case와 동일하다.

void selectionSort(int *arr, int N) {
	for (int i = 0; i < N - 1; i++) {			// 1. (N - 1) Times
		int minIndex = i;						// 2. (N - 1) Times
		for (int j = i + 1; j < N; j++) {		// 3. 1/2 * (N - 1)(N) Times
			if (arr[j] < arr[minIndex]) {		// 4. 1/2 * (N - 1)(N) Times
				minIndex = j;					// 5. 최대 (N - 1) Times
			}
		}
		swap(arr[i], arr[minIndex]);			// 6. (N - 1) Times
	}
}

• 위의 분석과 동일하게 총 비교 횟수와 실행 횟수가 계산된다.
• Worst Case에서는 배열이 역순으로 정렬되어 있어 minIndex가 항상 변경되므로 minIndex = j;가 최대 횟수로 실행된다.
• 그러나 시간 복잡도는 여전히 $O(N^2)$이다.

따라서 선택 정렬의 Worst Case 시간 복잡도는 다음과 같다.

$$ O\left(\frac{N(N - 1)}{2}\right) \approx O(N^2) $$

5. 결론

Selection sort는 구현이 간단하고 직관적인 정렬 알고리즘이지만, 시간 복잡도가 $O(N^2)$로 효율적이지 않다. 데이터의 크기가 작거나 메모리 공간이 제한적인 경우에만 사용이 권장된다. 이 알고리즘은 배열의 상태와 관계없이 항상 동일한 비교 횟수를 수행하므로, Best Case와 Worst Case의 시간 복잡도가 동일하다는 특징이 있다.