[Algorithm] 선택 정렬(Selection Sort) 코드와 시간 복잡도

인트로

기초 정렬 알고리즘인 선택 정렬(Selection Sort)과 시간 복잡도를 알아보자

 

 

선택정렬 활용 문제는 다음 포스팅을 참고하세요

[Algorithm] level0 : 3등의 성적은?

[Algorithm] level0 : 3등의 성적은?

 

선택정렬(Selection Sort) : 개념

1. 배열에서 최솟값을 찾는다.

2. 최솟값이 배열의 맨 앞 원소보다 작으면 자리를 교체한다.

3. 맨 앞의 원소를 제외한 체 1~2 과정을 반복한다.

https://velog.io/@idhyo0o/Algorithm-Sort

 

선택정렬(Selection Sort) : 코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, i, j, minIdx, tmp;

	cin >> n;

	vector<int> v(n);

	for (i = 0; i < n; i++)
		cin >> v[i];

	/*Selection Sort Begin*/
	for (i = 0; i < n - 1; i++)
	{
		minIdx = i;

		for (j = i + 1; j < n; j++)
		{
			if (v[minIdx] > v[j]) minIdx = j;
		}

		tmp = v[minIdx];
		v[minIdx] = v[i];
		v[i] = tmp;
	}
	/*Selection Sort End*/

	for (i = 0; i < n; i++)
		cout << v[i];
}

 

시간복잡도

첫 번째 회전(i == 0)에서 비교 횟수 1 ~ (N - 1) : N-1회

두 번째 회전(i == 1)에서 비교 횟수 2 ~ (N - 1) : N-2회

.

.

.

마지막 회전(i == N-2)에서 비교 횟수 : 1회

 

(N-1) + (N-2) + (N-3)... + 1 = N(N-1)/2

즉 시간 복잡도는 O(N^2)이다.

 

(+ 버블 정렬과 시간 복잡도는 동일하지만 자료의 Swap을 반복하는 버블 정렬보단 조금 빠르다.)

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html