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

1. 개념

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

2. 과정

1. 아직 정렬하지 않은 부분에서 최솟값을 선택한다.
2. 선택한 값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.
3. 위의 과정을 반복한다.

3. 구현

void selectionSort(int[] arr) {
	for(int i=0; i<arr.length-1; i++) {	// 1.
		int minIdx = i;
        for(int j=i+1; j<arr.length; j++) {	// 2.
        	if(arr[j] < arr[minIdx]) {	// 3.
            	minIdx = j;
            }
        }
        int temp = arr[minIdx];	// 4.
        arr[minIdx] = arr[i];
        arr[i] = temp;
	}
}

1. 정렬하지 않은 부분에서 최솟값을 선택하는 부분으로, 맨 왼쪽 원소의 값을 최솟값으로 가정하여 이 원소의 위치를 저장한다(minIdx). 처음에는 모든 원소가 정렬되지 않았기 때문에 인덱스 0부터 포함해주며, 배열의 크기-1까지 비교해준다. 비교 범위가 배열의 크기-1인 이유는 배열의 마지막 요소까지 반복문이 실행되면 이미 정렬된 상태에서 다시 한 번 더 최솟값을 찾아 교환하게 되는데, 이는 비효율적이므로 배열의 마지막 요소는 정렬이 필요하지 않다고 가정하기 때문이다.
2. 선택한 값의 다음 위치(i+1)부터 배열의 마지막 원소까지 최솟값과 비교를 한다.
3. 현재 위치의 값이 최솟값보다 작다면, 최솟값의 위치를 현재 위치로 갱신해준다.
4. 안쪽 반복문이 종료되면 선택한 값(arr[i])과 갱신된 위치의 값(arr[minIdx])을 교환해준다.

4. 성능 분석

/* 배열의 크기를 n으로 가정 */
for(int i=0; i<n-1; i++) {
	int minIdx = i;
	for(int j=i+1; j<n; j++) {
		if(arr[j] < arr[minIdx]) {
			minIdx = j;
		}
	}
	int temp = arr[minIdx];
	arr[minIdx] = arr[i];
	arr[i] = temp;
}

바깥 루프 i	안쪽 루프 j에서의 비교 횟수
i=0	n-1
i=1	n-2
i=2	n-3
...	...
i=(n-2)	1

• 총 비교 횟수 = 안쪽 루프 j에서의 비교 횟수의 합
  (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2
  ∴ 시간복잡도 O(n^2)

5. 특징

• 정렬할 때 주어진 배열 외에 다른 메모리 공간을 필요로 하지 않으므로 제자리 정렬 알고리즘이다.
• 최솟값을 찾는 과정이 데이터의 입력 상태에 민감하지 않기 때문에 언제나 동일한 시간 복잡도 O(n^2)을 갖는다.
• 동일한 값을 갖는 데이터가 여러 개 있을 때, 정렬 후 요소의 순서가 뒤바뀌므로 불안정적 정렬 알고리즘이다.

---

📖 참고

• Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱
• 선택 정렬 (Selection Sort)