[Java]선택 정렬(Selection Sort)

*선택 정렬(Selection Sort)

->선택 정렬이란 한 번의 배열 탐색에서 가장 작은 원소의 '위치'를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 방식을 사용(오름 차순으로 정렬하는 경우)하는 정렬 방식이다.

※가장 큰 원소의 위치를 찾고, 배열의 가장 마지막 원소부터 차례로 바꿔주는 방식을 사용해도 된다. 다만 반복문을 구현할 때 작은 원소의 값을 찾는 방식이 조금 더 구현하기 편하기 때문에 작은 원소를 찾는 방법을 주로 사용한다.

->말 그대로 큰 원소나 작은 원소를 선택하고 그 위치를 바꿔주기 때문에 선택 정렬이라는 이름을 사용한다.

 

*선택 정렬의 이해

->어떤 대상을 '오름차순'으로 정렬할 때 선택 정렬은 원소를 처음부터 탐색하면서, 작은 수를 찾고 그 수를 배열의 앞쪽과 차례로 보내는 방식을 사용한다. 예를 들어 [3, 1, 5, 7, 10]이라는 배열을 선택 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

초기 배열 상태

 우선, 첫 번째 원소의 값을 기억해두고 1번째 인덱스부터 4번째 인덱스까지 더 작은 값이 나올때마다 해당 위치의 인덱스를 기억해둔다. 따라서 우선 Array[MinIndex]에 대하여 Array[1]의 값을 비교하면 Array[1]의 값이 작기 때문에 Array[1]의 인덱스인 1을 기억해둔다.

Array[MinIndex] > Array[1]이므로, MinIndex = 1로 갱신해준다.

 마찬가지로 2번째 인덱스와 현재 Array[MinIndex]의 값을 비교해준다. 이때, Array[MinIndex]의 값이 더 작기 때문에 MinIndex의 값이 따로 갱신되지 않는다.

Array[MinIndex] < Array[2]이므로 MinIndex는 따로 갱신되지 않는다.

 3, 4번째 인덱스 역시 현재 Array[MinIndex]의 값보다 크기 때문에 MinIndex의 값은 따로 갱신이 일어나지 않는다.

Array[MinIndex] < Array[3], Array[MinIndex] < Array[4] 이므로 MinIndex는 따로 갱신되지 않는다.

 이렇게 한 번의 탐색이 완료되었을 때 최종적으로 해당 배열에서 가장 작은 값은 1번째 인덱스에 있는 값임을 알 수 있다. 따라서, 해당 값을 배열의 0번째 원소와 바꾸어 준다.

해당 배열에서 가장 작은 수는 1번째 원소이므로, 해당 값을 0번째 원소와 바꾸어준다.

 그리고 다음 반복해서는 초기 값을 1번째 인덱스부터 시작하여 마찬가지로 가장 작은 값을 앞으로 보내준다면 오름차순으로 정렬이 될 것이다.

 

*선택 정렬의 구현

package sort;

import java.util.Arrays;

public class SelectionSort {
	static int[] nums;

	public static void main(String[] args) {
		nums = new int[10];
		for (int i = 0; i < 10; i++) {
			nums[i] = (int) (Math.random() * 10);
		}
		System.out.println("<정렬 전>");
		System.out.println(Arrays.toString(nums));
		
		for(int i = 0; i < nums.length - 1; i++) {
			// 현재 탐색에서 가장 앞의 원소를 초기 값으로 설정해둔다.
			int MinIndex = i;
			// 탐색을 진행하며, 가장 작은 값을 찾는다.
			for(int j = i + 1; j < nums.length; j++) {
				if(nums[MinIndex] > nums[j])
					MinIndex = j;
			}
			// 탐색이 완료되면 가장 작은 값을 가장 앞의 원소와 가장 작은 원소의 위치를 바꾸어준다.
			int temp = nums[MinIndex];
			nums[MinIndex] = nums[i];
			nums[i] = temp;
		}
		
		System.out.println("<정렬 후>");
		System.out.println(Arrays.toString(nums));
	}
}

결과

*선택 정렬의 시간 복잡도

->버블 정렬과 마찬가지로 총 반복 횟수 = n(n-1)/2가 된다. 따라서, 선택 정렬의 시간 복잡도는 O(n^2)이다.

->선택 정렬은 어떤 정렬이 오더라도 비교하는 방식이 같기 때문에, 일반적인 상황에서 비슷한 성능을 보유한다.

->버블 정렬과 마찬가지로 직관적으로 이해가 편하고, 불필요하게 원소들을 교체하는 작업이 없기 때문에 버블 정렬보다 '일반적인 상황'에서 빠른 성능을 보이지만 여전히 시간 복잡도가 O(n^2)이기 때문에 실전에서 사용하기 힘든 정렬이다.