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

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

---

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자!

1, 10, 5, 8, 7, 6, 3, 4, 2, 9

가장 작은것을 앞으로 보내자!!!

1 10 5 8 7 6 3 4 2 9

1 2 5 8 7 6 3 4 10 9

1 2 3 8 7 6 5 4 10 9

1 2 3 4 7 6 5 8 10 9

⁞

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 8 9 10

소스코드 구현 (C++)

#include <iostream>
using namespace std;
int main()
{
	int min, index, temp;
	int arr[10] = { 1, 10, 5, 8, 7, 6, 3, 4, 2, 9 };
	//선택정렬
	for (int i = 0; i < 10; i++)
	{
		min = 9999;
		for (int j = i; j < 10; j++)
		{
			if (arr[j] < min)
			{
				min = arr[j];
				index = j;
			}
		}
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}

	//출력
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << ", ";
	}
	return 0;
}

결과 출력

시간 복잡도 계산

1, 10, 5, 8, 7, 6, 3, 4, 2, 9

10 + 9 + 8 + 7 +...+ 1

= 10 * (10 + 1) / 2 = 55

= N * (N + 1) / 2

시간 복잡도로 표현한다면

= O(N * N)

---

정렬만큼 알고리즘의 효율성 차이를 보여주는 것이 없기때문에 알고리즘의 시작은 정렬이라고 말할수 있다고 한다.

그중에서도 오늘은 선택정렬에 대해서 알아보았는데, 비효율적인 정렬방법 중 하나라고 할수 있다. 데이터의 갯수(N)가 증가 할수록 복잡도가 크게 증가하기 때문이다.