[정렬] 선택 정렬 (Selection Sort)

• 원소를 넣을 위치를 정해놓고 어떤 원소를 넣을지 찾아서 정렬한다.
• 오름차순의 경우, 가장 작은 값을 찾아서 왼쪽부터 정렬을 하거나, 가장 큰 값을 찾아 오른쪽부터 정렬을 하는 방식이다.

1. i = ( 1 ~ (n - 1) )인덱스까지 탐색

2. j = ( (i + 1) ~ n ) 인덱스까지 탐색

3. j의 값 중에 가장 작은 값을 찾아 i번째의 값과 위치를 바꾼다.

4. 위 과정 반복

---

코드 구현

#include <stdio.h>

void PrintArray(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Selection(int* arr, int size)
{


	int min, tmp;
	for (int i = 0; i < size - 1; i++)
	{
		min = i;
		for (int j = i + 1; j < size; j++)
		{
			if (arr[min] > arr[j]) min = j;
		}
		tmp = arr[min];
		arr[min] = arr[i];
		arr[i] = tmp;
		printf("%d번째 순회: ", i + 1);
		PrintArray(arr, size);
	}
}


int main(void)
{
	int arr[5] = { 42, 51,86, 12 ,31 };

	printf("정렬 전: ");
	PrintArray(arr, 5);

	Selection(arr, 5);

	printf("정렬 후: ");
	PrintArray(arr, 5);

	return 0;

}

결과

정렬 전: 42 51 86 12 31
1번째 순회: 12 51 86 42 31
2번째 순회: 12 31 86 42 51
3번째 순회: 12 31 42 86 51
4번째 순회: 12 31 42 51 86
정렬 후: 12 31 42 51 86

---

정리

 

• 시간 복잡도: (n - 1) + (n - 2) + ...... + 1 = n(n-1)/2 = O(n^2)