선택 정렬

동작

1. 입력 배열 내에서 최소값을 찾는다.
   • 오름차순 정렬의 경우. 내림차순 정렬일 경우 최소값이 아닌 최대값.
2. 해당 최소값을 배열의 첫 번째 요소와 자리를 바꾼다.
3. 입력 배열 내에서 두 번째로 작은 값을 찾는다.
4. 두 번째로 작은 값을 배열의 두 번째 요소와 자리를 바꾼다.

• 이를 $n-1$번 반복한다.
• 매 반복마다 최소값을 선택하고 배치하기 때문에 선택 정렬_{selection sort}이라 부른다.

분석

• 비교 횟수
  • 외부 루프는 $n-1$번 반복된다.
  • 내부 루프는 $n-1-i$번 반복된다.
  • ∴ 전체 비교 횟수 = $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2}$
    • 빅오 표기법으로 $O(n^2)$
• 교환 횟수
  • 외부 루프 실행 횟수와 동일하다. 즉 $(n-1)$번.
    • 빅오 표기법으로 $O(n)$
  • 단, 한 번의 교환에 3번의 이동이 필요하므로 전체 이동 횟수는 $3(n-1)$번.

특징

• 제자리 정렬이다.
• 자료 이동 횟수가 이미 결정되어 있다.
• 안정성을 만족하지 않는다.
• 최악, 평균, 최선 시간 복잡도가 모두 동일하다.
  • $O(n^2)$ 비교, $O(n)$ 교환
  • 다시 말해 이미 정렬된 배열이든 무작위로 나열된 배열이든 정렬에 걸리는 시간이 동일하다.

구현

public class SelectionSort {
	public static void sort(int[] array) {
		int n = array.length;
		for (int i = 0; i < n; i++) {
			int min = i;
			for (int j = i + 1; j < n; j++) { // 최소값 탐색
				if (array[j] < array[min])
					min = j;
			}
 
			// 배열의 앞부터 최소값과 교환
			int temp = array[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}