[기술공부]선택 정렬 (Selection Sort)

선택정렬은 현재 위치에 들어갈 데이터를 찾아 선택한 후 바꾸는 알고리즘이다.
데이터를 비교하면서 찾기 때문에 비교정렬이면서 정렬의 대상이 되는 데이터외에 추가적 공간을 필요하지 않기 때문에 제자리 정렬(in-place sort)이다.

불안정 정렬이다.
(int형일때는 상관없지만 문자열 형태의 key-value 형태 경우 순서가 바뀔 가능성이 있다.)

출처(나무위키)	출처(나무위키)

선택정렬은 2중 반복문으로 돌아갑니다.

최악의 경우에도 최선의 경우에도 O(N^2)의 시간이 걸리게 됩니다.

첫번째 위치부터 시작해서 현재위치 다음꺼부터 범위 끝까지 비교하여 최소값의 위치를 찾아 변수에 저장하며
이제 현재 index위치와 찾은 최소값 위치를 swap을 통하여 바꾸는데 이것을 처음부터 범위 끝까지반복하는것이 선택 정렬입니다.

구현 코드

public clasee selectSort{
	public static void Sort(int[] list){

        SelectSort sorter = new SelectSort();
        sorter.selectionSort(list);
    }
    
    private void selectionSort(int[] list) {
        int indexMin; 
        for (int i = 0; i < list.length - 1; i++) {
            indexMin = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[indexMin]) {
                    indexMin = j;
                }
            }
            swap(list, i, indexMin);
        }
    }
    
    private void swap(int[] list, int indexMax, int indexMin){
    	int temp = list[indexMin];
        list[indexMin] = list[indexMax];
        list[indexMax] = temp;
    }
}

[장점]
1. 추가적인 메모리 소비가 작다.

[단점]
1. 시간복잡도가 O(N2) 이다.
2. 안정 정렬이 아니다.