Selection Sort

2024-10-01algorithm

📚 algorithm

알고리즘의 점근적 분석2024-09-29
알고리즘의 재귀적 분석2024-09-30
Selection Sort2024-10-01
Insertion Sort2024-10-02
Merge Sort2024-10-04
Linear-time selection2024-10-20

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. 귀납적 증명의 구성 요소

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

기저 사례(Base Case): P(0)이 참임을 보인다.
귀납 가정(Inductive Hypothesis): 임의의 자연수 k에 대해 P(k-1)가 참이라고 가정한다.
귀납 단계(Inductive Step): P(k-1)가 참일 때 P(k)도 참임을 보인다.
종료성(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
	}
}

for (int i = 0; i < N - 1; i++)
- (N - 1) 번 실행된다.
int minIndex = i;
- (N - 1) 번 실행된다.
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}$ 번 실행된다.
if (arr[j] < arr[minIndex])
- 내부 루프와 동일하게 $\frac{N(N - 1)}{2}$ 번 실행된다.
minIndex = j;
- 배열이 이미 정렬된 경우에는 조건이 항상 거짓이므로 이 부분은 실행되지 않는다.
- 하지만 Best Case에서도 비교 횟수는 동일하므로 시간 복잡도에 영향이 없다.
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의 시간 복잡도가 동일하다는 특징이 있다.

📚 algorithm

알고리즘의 점근적 분석2024-09-29
알고리즘의 재귀적 분석2024-09-30
Selection Sort2024-10-01
Insertion Sort2024-10-02
Merge Sort2024-10-04
Linear-time selection2024-10-20