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

선택정렬의 종류

① 최소값 선택 정렬 (오름차순)
② 최대값 선택 정렬 (내림차순)

 

최소값 선택 정렬 (오름차순)

1. 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다.
2. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다.
3. 모든 숫자를 옮길 때까지 반복한다.

최소값 선택정렬

 

최대값 선택 정렬(내림차순)

1. 정렬되지 않은 숫자 중 가장 큰 숫자를 선택한다.
2. 선택한 가장 큰 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다.
3. 모든 숫자를 옮길 때까지 반복한다.

최대값 선택정렬

정확성 증명

 i번째 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명

 

성능분석

n개가 있을 때 가장 큰/작은 수를 구하기 위해서 n-1 번의 비교가 일어남.  => n(n-1) / 2
O(n²)

내가 구현한 소스 (JAVA)

	public int[] solution(int n, int[] arr) {
		for(int i = 0; i<n-1; i++) {
			//1. 최소값 구하기
			int min = arr[i];
			int minIndex = i;
			for(int j=i+1; j<n; j++) {
				if(min>arr[j]) {
					min = arr[j];
					minIndex = j;
				}
			}
			//2.자리바꾸기
			int tmp = arr[i];
			arr[i] = min;
			arr[minIndex] = tmp;
		}
		
		return arr;
	}