선택 정렬(Selection Sort)#

작동 원리#

¹

선택 정렬은 간단한 정렬 알고리즘으로, 목록을 N-1번 순회하면서 각 단계마다 남은 요소들 중 최솟값을 찾아 현재 위치와 교환하는 방식으로 동작한다. 구체적으로, 첫 번째 위치(0)부터 시작하여 전체 목록에서 최솟값을 찾아 해당 위치와 교환하고, 그 다음에는 두 번째 위치(1)부터 시작하여 남은 요소들 중 최솟값을 찾아 교환하는 과정을 N-1번째 위치까지 반복한다. 이처럼 최솟값을 선택하여 정렬하는 특성 때문에 ‘선택 정렬’이라는 이름이 붙었다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)#

• 평균 수행 시간: $O(N^2)$
• 최악 수행 시간: $O(N^2)$
• 메모리(공간 복잡도): $O(1)$
• 안정성: X

코드#

public class SelectionSort implements Sort{  
    @Override  
    public int[] sort(int[] array) {  
        for(int j = 0; j< array.length-1; j++){  
            int min = 1000000000;  
            int minIndex = 0;  
            for(int i = j; i<array.length; i++){  
                if(min > array[i]){  
                    min = array[i];  
                    minIndex = i;  
                }  
            }  
            int temp = array[j];  
            array[j] = array[minIndex];  
            array[minIndex] = temp;  
        }  
        return array;  
    }  
}

코드는 다음 레포의 study_1 브랜치에서 확인해볼 수 있다.