선택정렬 selection sort

선택정렬의 종류

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

 

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

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

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

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

시간복잡도

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;
	}

 

출처

• 컴퓨터 알고리즘 기초 3강 정렬문제, T아카데미