2. 정렬 알고리즘 - 선택정렬

정렬이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

오름차순이나 내림차순 등 어떤 식으로든 정렬해서 사용하는 경우가 많다.

선택정렬

가장 작은 것을 선택한다는 의미

1회전: 전체 데이터 중 가장 작은 데이터를 선택한다. '3'
맨 앞에 있는 '9'와 '3'을 바꾼다.

2회전: 정렬된 첫 번째는 제외하고 이후 데이터 중 가장 작은 데이터를 선택한다. '5'
'6'과 '5'를 바꾼다.

3회전: 최솟값 탐색 '6'
'7'과 '6'을 바꾼다.

4회전: 최솟값 탐색 '7'
'9'와 '7'을 바꾼다.

선택정렬 c++ 코드 (오름차순)

#include <iostream>
using namespace std;

int main()
{
	int arr[10] = { 4,3,2,5,6,1,7,8,9,0 };
	for (int i = 0; i < 10; i++)
	{
		int min_index = i;
		for (int j = i + 1; j < 10; j++)
		{
			if (arr[min_index] > arr[j])
				min_index = j;
		}
		swap(arr[i], arr[min_index]);
	}
	for (int i = 0; i < 10; i++)
		cout << arr[i] << ' ';
}

선택정렬 c++ 코드 (내림차순)

#include <iostream>
using namespace std;

int main()
{
	int arr[10] = { 4,3,2,5,6,1,7,8,9,0 };
	for (int i = 0; i < 10; i++)
	{
		int min_index = i;
		for (int j = i + 1; j < 10; j++)
		{
			if (arr[j] > arr[min_index])
				min_index = j;
		}
		swap(arr[i], arr[min_index]);
	}
	for (int i = 0; i < 10; i++)
		cout << arr[i] << ' ';
}

선택정렬의 시간복잡도

O(N^2)의 시간복잡도 --> 간단하지만 매우 비효율적