선택 정렬(Selection Sort)

가장 작은 것을 선택해서 앞으로 보낸다.

선택 정렬은 가장 작은 것을 선택하여 앞으로 보내는 방식의 정렬 방법이다. 즉, 작은 순서대로 하나씩 인덱스를 선택하여 해당 위치의 인덱스와 위치를 변경하며 정렬하는 방법이다.

---

예시 문제:

1 10 5 4 3 2 9 6 7 8

해당 숫자를 오름차순으로 정렬하시오.

이를 선택 정렬로 문제풀이를 하면 다음과 같은 순서를 따른다.

1번 선택:
1 10 5 4 3 2 9 6 7 8
1 선택 시 1이 가장 앞에 있으므로 변화가 없다.

2번 선택:
1 10 5 4 3 2 9 6 7 8 => 1 2 5 4 3 10 9 6 7 8
2 선택 후 2번 자리에 있는 10과 위치를 바꾼다.

3번 선택:
1 2 5 4 3 10 9 6 7 8 => 1 2 3 4 5 10 9 6 7 8
3 선택 후 3번 자리에 있는 5와 위치를 바꾼다.

...

이런 식으로 10번 자리까지 반복한다.

---

이를 코드로 표현해 보면

//C++로 작성
#include <stdio.h>

int main(){
	int i, j, index, min, temp; 
    
    int arr[10] = {1, 10, 5, 4, 3, 2, 9, 6, 7, 8};
    for(i=0;i<10;i++){
    min = 999999 //min에 그냥 큰 값을 넣어놓기 위해.
    	for(j=i;j<10;j++){
        	if(min>arr[j]){
            	min = arr[j];
                index = j;
            }
        }
        //swap
        temp = arr[i];
        arr[i] = arr[index];
        arr[index]=temp;
    }
    for(i=0;i<10;i++){printf("%d",arr[i]);}
    return 0;
}

#파이썬 코드로 작성.
1_list = [1, 10, 5, 4, 3, 2, 9, 6, 7, 8]

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        # swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

selection_sort(1_list)
print(1_list)


=> 이 코드의 시간 복잡도 계산.
우선, 이 배열은 1~10 까지의 원소를 가진다.
그러면, 10, 9 ,8, 7, ~~ , 1 이렇게 반복문 연산을 수행한다.

이는 등차수열 계산과 같다.
이는 10 * (10+1)/2 = 55 의 계산이 된다.

시간 복잡도는  N * (N+1)/2 인데, 컴퓨터 수학에서는 N이 무수히 큰 수라고 가정할 때 '+' 연산이나 '/2' 정도는 큰 차이가 없는 것으로 판단하여 무시하기 때문에 N*N 으로 표기한다.

따라서 시간 복잡도는 **O(N^2)** 가 된다.

이 선택 정렬은 데이터 값이 커질 수록 시간 복잡도가 굉장히 커지므로(연산 횟수가 커지므로), 매우 비효율적인 알고리즘이다.