[알고리즘] - 선택 정렬 (Selection Sort)

1. 선택 정렬(Selection Sort)이란?

정렬되지 않은 데이터 중에서 최솟값을 찾아 맨 앞 원소와 위치를 교환시키는 방법

제자리 알고리즘 (in-place algorithm) 에 해당한다. 

제자리 알고리즘 (in-place algorithm)이란?
입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 말한다.

 

알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 

---

2. 선택 정렬의 수행 방식

선택 정렬 과정

① 정렬할 범위 안에서 최솟값을 찾는다. (내림차순인 경우 최댓값을 찾으면 된다.)

② 정렬할 부분 중 가장 앞에 있는 데이터와, ①에서 구한 데이터를 swap한다.

③ 정렬할 범위는 1 감소한다. → (맨 앞 데이터의 다음 데이터 ~ 맨 끝)

④ 새로운 정렬할 범위를 얻었다. 남은 정렬 부분이 없을 때까지 다시 ①부터 반복한다.

 

 

 

---

3. 선택 정렬 구현 (C++)

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

//선택 정렬 함수(여기서 n은 배열의 크기)
void selection_sort(int arr[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int min = i;
		
        	//정렬할 범위 안에서 최솟값 구하기
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}

		//구한 최솟값을 정렬할 범위의 맨 앞 원소와 swap
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int list[10] = { 12,28,9,1,6,32,56,44,19,20 };

	cout << "정렬 전" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}

	selection_sort(list, 10);

	cout << "\n\n정렬 후" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}

}

실행 결과 정상적으로 선택 정렬이 수행된 것을 확인할 수 있다.