선택 정렬(Selection Sort)

단순 선택 정렬

단순 선택 정렬은 요소를 검사하면서 가장 작은 요소부터 정렬하는 알고리즘이다.
아래 그림과 같이 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고 아직 정렬되지 않은 부분의 첫 번째 요소와 교환한다.

• 코드

void selection(int a[], int n) { 
	for (int i = 0; i < n; i++) {
		int min = i; // 아직 정렬되지 않은 위치로 초기화
		for (int j = i + 1; j < n; j++) 
			if (a[j] < a[min]) 
				min = j; // 가장 작은 값의 인덱스 저장
		swap(int, a[i], a[min]); // 가장 작은 값과 정렬되지 않은 첫 번째 요소 교환
	}
}

• 단순 선택 정렬 교횐 과정

1. 아직 정렬되지 않은 부분에서 가장 작은 키의 값 a[min]을 선택
2. a[min]과 아직 정렬되지 않은 부분의 맨 처음 요소 교환

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

• 장점
  비교횟수는 많으나 교환 횟수가 상당히 적다. 따라서 교환이 많이 이루어져야하는 자료 상태에서 가장 효율적으로 적용될 수 있는 정렬 방식이다. 아래 그림과 같은 역순정렬일때 적합하다.

• 단점
  

1. 서로 떨어져 있는것을 교환하기 때문에 같은 값이 데이터안에 존재할 경우 순서가 바뀔수 있어 불안정적이다. 아래그림 참고(정렬전 왼쪽 3, 오른쪽 3 다른색 표시)
2. 정렬되어 있는 상태에서 소수의 작은 데이터를 추가하고 다시 정렬할때 최악의 효율을 나타낸다.