[Algorithm] Basic Sort Algorithm - Selection Sort (선택 정렬)

배열 중 가장 큰 원소를 오른쪽부터 채워가며 숫자를 정렬하는 방법

 

각 루프마다

- 최대 원소 찾기

- 최대 원소 <-> 맨 오른쪽 원소 교환

- 맨 오른쪽 원소 제외

Selection sort

public void selectionSort(int[] arr) {
	if (arr.length == 0 ) {
		return;
	}
	
    	System.out.print("[정렬할 원소] ");
	print(arr);
    
	int max;
	
	for (int last = arr.length-1; last>0; last--) { // 1
		max = last - 1;
		
		// 마지막을 제외한 나머지 element 중 가장 큰 수 찾기
		for (int k = last-1; k >= 0; k--) {		// 2
			if (arr[k] > arr[max]) {
				max = k;
			}
		}
		
		if (arr[max] > arr[last] ) {	
			swap(arr, max, last);		// 3
		}
		
		System.out.print(arr.length - last + "단계 : ");
		print(arr);
	}

}

 

실행 시간

1번의 for 루프 n-1 번 반복

2번에서 가장 큰 수를 찾기 위한 비교 횟수: n-1, n-2, ..., 2, 1

3번의 교환은 상수시간 작업

 

시간 복잡도: T(n) = (n-1)+(n-2)+...+2+1 = n(n-1)/2 = O(n^2)

 

 

 

 

 

Ref. https://www.youtube.com/watch?v=0dG7xTt5IfQ