Seletion Sort (선택정렬)

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

 

배열의 최소값을 찾은 후, 왼쪽부터 정렬하기. -> 선택정렬

시간 복잡도 : 최소값을 찾는 비교 과정에서 왼쪽 부분에 데이터가 하나 정렬될 때마다 (n-1)+(n-2)+....

-> (n-1)+(n-2)+(n-3)+.....1 = n*(n-1)/2 -> O(n^2) 

 

Code

#include <iostream>
using namespace std;

#define size 10

int main()
{
	int arr[size] = {4, 2, 6, 7, 3, 1, 5, 9, 8, 10};
	int temp = 0, min = 0;

	cout << "정렬 전 : ";

	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";

	for (int i = 0; i < size; i++)
	{
		min = i;

		for (int j = i + 1; j < size; j++)
		{
			if (arr[min] > arr[j])
				min = j;
		} // for
		swap(arr[i], arr[min]);
	}
	cout << "\n정렬 후 : ";

	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
}