[알고리즘] 선택정렬 (selection sort)

 

선택 정렬이란?

선택 정렬은 배열을 정렬할 때 가장 작은(혹은 가장 큰) 값을 찾아 배열의 맨 앞부터 차례로 정렬하는 방식입니다. 이름에서 알 수 있듯이, 값을 선택(select)하고 이를 적절한 위치로 옮기는 과정이 반복됩니다.

간단한 동작 원리:

1. 주어진 배열에서 가장 작은 값을 찾습니다.
2. 그 값을 배열의 맨 앞에 위치한 값과 교환(swap) 합니다.
3. 배열의 두 번째 위치부터 위 과정을 반복하며, 끝까지 진행하면 정렬이 완료됩니다.

---

선택 정렬의 동작 과정

예를 들어, 배열 [64, 25, 12, 22, 11]를 오름차순으로 정렬해 보겠습니다.

1. 첫 번째 단계
   • 배열 전체를 탐색하여 가장 작은 값 11을 찾습니다.
   • 11을 첫 번째 위치(64)와 교환합니다.
   • 배열 상태: [11, 25, 12, 22, 64]
2. 두 번째 단계
   • 나머지 배열 [25, 12, 22, 64]에서 가장 작은 값 12를 찾습니다.
   • 12를 두 번째 위치(25)와 교환합니다.
   • 배열 상태: [11, 12, 25, 22, 64]
3. 세 번째 단계
   • 나머지 배열 [25, 22, 64]에서 가장 작은 값 22를 찾습니다.
   • 22를 세 번째 위치(25)와 교환합니다.
   • 배열 상태: [11, 12, 22, 25, 64]
4. 네 번째 단계
   • 마지막으로 [25, 64]에서 가장 작은 값 25를 유지합니다.
   • 배열은 이미 정렬된 상태입니다: [11, 12, 22, 25, 64]

---

선택 정렬의 코드 구현

선택 정렬의 코드는 간단합니다. C++로 구현해 보겠습니다.

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

void selection_sort(int ary[], int size) {
	int min, temp; //최솟값의 인덱스를 저장할 min과 값swap을 위한 temp 변수 선언
	for (int i = 0; i < size - 1; i++) { // 배열의 첫 값부터 최대 크기 - 1만큼 반복 
		min = i;
		for (int j = i + 1; j < size; j++) { // i+1부터 배열의 최대크기만큼 반복
			if (ary[j] < ary[min]) // 가장 작다고 생각했던 값보다 더 작은 값이 존재하면?
				min = j; // 그 인덱스를 min에 넣는다.
		}
		temp = ary[i]; // 탐색 과정 종료 후, swap 과정
		ary[i] = ary[min];
		ary[min] = temp;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int ary[5] = { 64, 25, 12, 22, 11};
	selection_sort(ary, 5);
	for (int i = 0; i < 5; i++) 
		cout << ary[i] << ' ';

	return 0;
}