[알고리즘]선택 정렬(SelectionSort) 개념 정리 및 코드 리뷰

감자 코딩에 감자 개발자입니다.  이번에 살펴볼 내용은 알고리즘의 Sort중 하나인 선택정렬(SelectionSort)입니다.

1.선택정렬(SelectionSort) 시간복잡도와 공간복잡도 

선택정렬(SelectionSort)의 시간복잡도는 O(N^2) 공간복잡도는 하나의 배열만을 사용하여 정렬하기 때문에 O(N)입니다.

2. 선택정렬 원리

크기가 N인 배열 1,2,3......N까지의 배열이 있다고 생각을 해봅시다.

이제 처음부터 비교를 하기 시작합니다. 

1. 맨처음 Index[0] 값을 기준으로 index[1], index[2] ...... index[N]까지의 값들을비교합니다. 

2. 이중에서 Index[0] 값과 비교하여 가장 작은수를 index[0]와 위치를 변경해줍니다.

3. 그다음 Index[1]을 Index[0]와 같은 방식으로 비교해나가면서 가장 작은수를 Index[1]와 바꾸어줍니다.

4. 이렇게 Index[N-1]까지 최종적으로 Index[N]과 비교를 하여 작은수를 바꾸어주면 선택정렬은 종료하게 됩니다.

예) 크기가 5인 배열 50,40,30,20,10

1) 50 -> 40 30 20 10 비교하여 가장작은값 50과 위치 변경 ( 10 40 30 20 50)

2) 40 -> 30 20 50 비교하여 가장작은값 20과 위치 변경 ( 10 20 30 40 50)

3) 30 -> 40 50 비교하여 가장 작은값을 확인하려고 했으나, 가장작은 값이므로 건너뛴다. (10 20 30 40 50)

4) 40 -> 50 비교 하여 가장작은값은 이미 40이므로, 건너뛴다. (10 20 30 40 50)

5) 50 -> 종료 ( 10 20 30 40 50)

3. 선택 정렬의 코드

// comment: Selection_Sort
public static void Selection_Sort(int[] input){
    int temp;           // comment: Swap Variable

    // comment: 시간복잡도 O(n^2)
    for(int i=0; i<input.length - 1; i++){
        // comment: 하나씩 제외하면서 순회해야하기때문에 i는 0부터 시작하고있으므로, i+1부터 시작해야 1번인덱스부터 비교가능
        // comment: 정렬된것들 (맨앞에 있는 값)들을 제외하면서 순회하기 위해서 for 루프
        for(int j=i+1; j<input.length; j++){
            if(input[i] > input[j]){
                temp = input[j];
                input[j] = input[i];
                input[i] = temp;
                
            }

        }
    }
}