[알고리즘] 선택 정렬 알고리즘

정렬은 자료 탐색에서 매우 중요한 알고리즘이다. 국어사전을 예로 들어보자 만약 국어사전이 가나다 순으로 오름차순이나 내림차순 정렬이 되어 있지 않다면 단어를 빨리 찾는 것은 매우 어려울 것이다. 정렬 알고리즘은 여러 가지가 있지만 이번에 다룰 알고리즘은 선택 정렬 알고리즘이다.

1. 선택 정렬 알고리즘이란?

선택 정렬은 매번 정렬이 안 된 값 중 가장 작은 값을 차례차례 앞에 배치시키는 정렬 방법이다. 오름차순으로 정렬한다고 가정하고 설명해보겠다.

검정색으로 표시한 부분은 정렬이 완료된 부분, 남색 부분은 정렬이 안된 부분이다. 매 스캔마다 정렬이 안된 부분(남색) 중 가장 작은 값을 찾아 정렬이 안된 부분(검정색)의 첫번째 인덱스에 배치하는 것을 확인할 수 있다.

2. 소스 코드 구현

구현하는데 사용한 언어는 C++이다.

void selection_sort(int* arr, int n) {
	for (int i = 0; i < n - 1; i++) {
		int least = i;
		for (int j = i + 1; j < n; i++) {
			if (arr[j] < arr[least]) {
				least = j;
			}
		}
		swap(a[i], a[least]);
	}
}

인덱스 i는 배열의 시작부터 시작해 배열의 끝의 앞 인덱스까지 증가한다. 안쪽 for문에서 매 스캔마다 가장 작은 값 arr[least]를 찾는 것을 볼 수 있다. 그렇게 가장 작은 값을 찾게 되면 현재 인덱스 i의 값과 교환을 해줌으로써 차례차례 정렬을 완료하게 된다.

#include <iostream>
using namespace std;

void print_array(int* arr, int n) {
	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}

void selection_sort(int* arr, int n) {
	for (int i = 0; i < n - 1; i++) {
		int least = i;
		for (int j = i + 1; j < n; i++) {
			if (arr[j] < arr[least]) {
				least = j;
			}
		}
		swap(a[i], a[least]);
	}
}

int main() {
	int arr[6] = { 3, 4, 1, 5, 9, 7 };
	cout << "정렬 전 -> ";
	print_array(arr, 6);

	cout << "정렬 후 -> ";
	selection_sort(arr, 6);
	print_array(arr, 6);

	return 0;
}

예제를 실행시킬 수 있는 전체 코드이다.

3. 관련 포스트

[알고리즘] 버블 정렬 알고리즘
[알고리즘] 삽입 정렬 알고리즘

4. 참조

천인국, 최영규, 「C++로 쉽게 풀어쓴 자료구조」, 생능출판사, 2019년