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

선택정렬

• 해당 순서에 원소를 넣을 위치를 정하고, 어떤 원소를 넣을지 선택하는 알고리즘

---

과정

1. 주어진 배열에서 최소값을 찾는다.
2. 선택된 값을 현재 순서의 위치의 값과 교체한다.
3. 다음위치로 이동한다.
4. 해당과정을 배열 끝위치의 앞까지 이동할 때까지 반복한다.

---

특징

• 장점
  - 구현하기 쉽다.
  - 제자리 정렬(in-place sorting) 알고리즘. 추가로 메모리를 필요로 하지 않는다.
  
  
• 단점
  - 불안정 정렬(Unstable Sort) 이다.
  
  
  정렬을 위한 비교 횟수는 많지만, 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

---

코드

구현(C++)

void SelectionSort(int arr[], size_t arr_size) {

	int min_idx;

	for (size_t i = 0; i < arr_size-1; i++) {

		min_idx = i;

		for (size_t j = i + 1; j < arr_size; j++)
			if (arr[j] < arr[min_idx])
				min_idx = j;

		swap(arr[i], arr[min_idx]);
	}
}