선택 정렬 (Selection sort)

원소를 넣을 위치를 정한 후, 정렬된 원소를 제외한 나머지 원소들을 순회하며 가장 적은 원소를 선택하고 삽입하며 정렬하는 알고리즘

정렬 과정

1. 첫 번째 원소부터 마지막 원소를 순회하며 최솟값을 찾아 맨 앞의 원소와 자리를 바꾼다.
2. 정렬된 첫 번째 원소를 제외한 두 번째 원소부터 마지막 원소를 순회하며 최솟값을 찾아 두 번째 원소와 자리를 바꾼다.
3. 위의 과정을 마지막 인덱스까지 진행한다.
   
   

소스 코드

void SelectionSort() {		
	int[] nums = {1000, 400, 12, -59, 328, 121, -3};
	int size = nums.length;
    
    	// loop 1
	for(int i = 0; i < size; i++) {
		int minIdx = i;
        
        	// loop 2
		for(int j = i; j < size; j++) {
			if(nums[minIdx] > nums[j]) {
				minIdx = j;
			}
		}
			
            	// conditional 1
		if(minIdx != i) {
			int temp = nums[i];
			nums[i] = nums[minIdx];
			nums[minIdx] = temp;
		}
	}
		
	System.out.println(Arrays.toString(nums));
}

loop 1: 원소를 넣을 위치를 의미한다.
loop 2: 현재 위치의 원소부터 마지막 원소를 순회하며 최솟값의 위치를 찾는다.
conditional 1: 최솟값의 위치가 현재 위치와 다르다면, 두 원소의 자리를 바꿔준다.

시간 복잡도

각 회전에서의 비교 횟수를 더해보면 위와 같으므로, 모든 경우에서 O(N^2) 이다.

공간 복잡도

단 하나의 배열에서만 진행되므로 O(n) 이다.

장점

• 구현이 단순하다.
• 교환 횟수가 적어 많은 교환이 필요한 상태에서 비교적 효율적이다.
• 제자리 정렬(in-place sorting) 이므로 다른 메모리 공간을 필요로 하지 않는다.
  
  

단점

• 시간 복잡도가 모든 경우에서 O(N^2) 이므로 매우 비효율적이다.
• 불안정 정렬(Unstable sort) 이다.
  
  

[참고]

• 선택 정렬(Selection Sort)