Selection Sort - 선택 정렬

소개

특정 인덱스 값의 값을 남은 값들을 순회 하면서 가장 크거나 작은 값으로 바꾸는 정렬 알고리즘으로, 메모리가 제한적인 경우 사용하면 성능 상 이점이 있는 알고리즘이다.

설명

1. 주어진 데이터의 첫번째 인덱스의 값을 첫번째를 제외한 나머지 데이터 중에서 가장 크거나 작은 값으로 변경한다

2. 순회를 끝내면 인덱스 값을 증가 시켜서 나머지 데이터 중에서 가장 크거나 작은 값으로 변경한다. 

3. 위의 동작을 순회가 끝날때 까지 반복한다.

시간복잡도

선택정렬 또한 순회를 할 때마다 -1씩 순회 할 데이터 양이 줄어 든다. 그러면 다음과 같은 수식을 얻을 수 있게 된다. $(n-1) + (n-2) + ... + 2 + 1 = (n - 1) * n / 2 = (n^2-n)/2$ 그래서 선택정렬의 시간 복잡도는 $O(n^2)$이다.

소스코드

public class SelectionSort {
	public static void main(String[] args) {
		int[] values = ;
		
		for(int i=0; i<values.length-1; i++) {
			int minIndex = i;
			for(int j=i+1; j<values.length; j++) {
				if(values[j] < values[minIndex]) {
					minIndex = j;
				}
			}
			
			int tmp = values[minIndex];
			values[minIndex] = values[i];
			values[i] = tmp;
		}
		
		for(int i=0; i<values.length; i++) {
			System.out.println(values[i]);
		}
	}
}

참고 자료

위키백과 - 선택정렬