[Sort] Selection Sort

- 선택 정렬은 작은 양의 데이터에 유용.

 

- 구현이 쉽고 제자리 정렬(추가 저장 공간이 필요 없음)

  --> bubble sort나 insertion sort 등도 마찬가지. 그냥 temp 변수 선언으로 치환 할 뿐.

 

알고리즘

 1. 목록에서 최소값을 찾는다.

 2. 찾은 최소값을 맨 앞의 값(혹은 현재 위치의 값)과 교체

 3. 배열의 전체 요소가 정렬될 때까지 이 과정을 반복.

 

- 시간 복잡도

   Worst: O(n^2)

   Best: O(n)

   Average: O(n^2)

   

- 공간 복잡도: O(1)

 

void selection_sort(int arr[], int size_arr) {

	for (int i = 0; i < size_arr; i++) {
		int min = i;   
		for (int j = i + 1; j < size_arr; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}
		int temp = arr[min];
		arr[min] = arr[i];
		arr[i] = temp;
	}
	print_arr(arr, size_arr);
}