[자료구조&알고리즘] 선택 정렬

1. 선택 정렬

선택 정렬은 리스트를 순차적으로 탐색하여 가장 작은 또는 가장 큰 요소를 선택하고, 이를 정렬되지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다. 이렇게 하면 리스트의 정렬되지 않은 부분이 점점 줄어들고, 결국 리스트 전체가 정렬된다. 

선택 정렬의 시간 복잡도는 O(n^2)이다. 이는 두 개의 중첩된 반복문으로 인해 발생하는데 첫 번째 반복문은 리스트의 모든 요소를 반복하며, 두 번째 반복문은 나머지 요소들 중에서 최소값을 찾는다. 선택 정렬은 정렬된 상태와 상관없이 항상 동일한 시간 복잡도를 가지므로, 데이터의 초기 상태에 크게 영향을 받지 않는다.

 

2. 구현 방식

2.1 주어진 리스트에서 최소값을 찾습니다.

2.2 그 최소값을 리스트의 첫 번째 요소와 교환합니다.

2.3 리스트의 첫 번째 요소를 제외하고 나머지 리스트에서 다시 최소값을 찾아 두 번째 요소와 교환합니다.

2.4 이 과정을 리스트 끝까지 반복합니다.

3. 문제 예제

3.1 백준 2750번

https://www.acmicpc.net/problem/2750

 

 

3.1.1 구현 방식

#include <iostream>
#include <vector>

using namespace std;

void SelectionSort(vector<int>& A)
{
	int n = A.size();

	//마지막 요소는 자동으로 제자리에 있기 때문에 비교할 필요가 없다.
	//따라서 n-1 까지 반복한다.
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (A[j] < A[min])
				min = j;
		}

		swap(A[min], A[i]);
	}
}

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

	int N;
	cin >> N;

	vector<int> A(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	SelectionSort(A);

	for (const int& num : A)
	{
		cout << num << endl;
	}
}