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

선택 정렬(Selection Sort)

 

선택 정렬(Selection Sort) 이란?

 

 - 정렬 순서에 맞게 하나씩 선택해서 옮기는 정렬 방법이다.

 

 - 정렬 순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 자리에 가져다 놓는다.

 

 - N개의 데이터가 주어졌을 때의 O($N^2$)시간 복잡도를 가진다.

 

---

 

선택 정렬의 예시(오름차순)

1. 초기 상태

 

2. 탐색 범위에서 가장 가장 작은 값(1)을 현재 위치(1번째)의 값(7)과 바꾼다.

 

 

 

3. 탐색 범위에서 가장 가장 작은 값(3)은 현재 위치(2번째) 값(3)과 같기 때문에 교환이 일어나지 않는다.

 

aa

4. 탐색 범위에서 가장 가장 작은 값(5)은 현재 위치(3번째) 값(5)과 같기 때문에 교환이 일어나지 않는다.

 

5. 탐색 범위에서 가장 가장 작은 값(7)을 현재 위치(4번째)의 값(8)과 바꾼다.

6. 최종 결과(마지막 인덱스에서는 탐색하지 않는다.)

 

---

 

선택 정렬 코드(C++)

 

#include <iostream>
#include <vector>

using namespace std;

void SelectionSort(vector<int> &selectVec)
{
	int maxSize = selectVec.size();
	int tmp = 0;
	int minIndex = 0;
	for (int i = 0; i <maxSize-1; i++)
	{
		minIndex = i;
		for (int j = i+1; j < maxSize; j++)
		{
			// 최소 값 찾기
			if (selectVec[minIndex] > selectVec[j])
			{
				minIndex = j;
			}
		}

		// 최소 값이 자기 자신이 아닐 경우 위치 교환
		if (i != minIndex)
		{
			tmp = selectVec[i];
			selectVec[i] = selectVec[minIndex];
			selectVec[minIndex] = tmp;
		}
	}
}


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

	vector<int> selectVec{ 7,3,5,8,1 };

	cout << "== 정렬 전 ==\n";

	for (auto n : selectVec)
		cout << n << endl;;

	SelectionSort(selectVec);
	
	cout << "== 정렬 후 ==\n";

	for (auto a : selectVec)
		cout << a << endl ;

	return 0;
}

 

 

실행 결과