[Sorting] 선택 정렬 (Selection sort)

다음 리스트를 선택정렬로 오름차순으로 정렬해보자.

 

list = [13, 4, 8, 20, 37, 17]

 

How? 가장 작은 쪽, 즉 0번 인덱스부터 시작해서 해당 자리에 들어올 가장작은 값을 선택한 뒤, 자리를 바꾼다.

 

 [13, 4, 8, 20, 37, 17]

13에 들어올 값을 탐색한다. 1번 ~ 5번 인덱스 값 중 가장작은 값은 4이다.

13과 4의 자리를 바꾼다.

[4, 13, 8, 20, 37, 17]

 

 

[4, 13, 8, 20, 37, 17]

13에 들어올 값을 탐색한다. 2번 ~ 5번 인덱스 값 중 가장작은 값은 8이다.

13과 8의 자리를 바꾼다.

 [4, 8, 13, 20, 37, 17]

 

 

 [4, 8, 13, 20, 37, 17]

13보다 작은 값이 없으므로 이 자리는 교환하지 않고 13으로 고정한다.

[4, 8, 13, 20, 37, 17]

 

[4, 8, 13, 20, 37, 17]

20에 들어올 값을 탐색한다. 4번 ~5번 인덱스 값 중 가장작은 값은 17이다.

[4, 8, 13, 17, 37, 20]

 

[4, 8, 13, 17, 37, 20]

37에 들어올 값을 탐색한다. 5번 인덱스 값 20과 자리를 바꾼다.

[4, 8, 13, 17, 20, 37]

 

정렬된 리스트 : [4, 8, 13, 17, 20, 37]

 

시간 복잡도 (Time Complexity)

O(n²)

: 리스트에 있는 모든 아이템을 체크해야 하므로 n이 필요하며, 그 아이템마다 자리를 바꿀 최솟값을 찾는데 n이 필요하다.

 

코드 구현

for(int i = 0; i < n-1; i++){
	int idx = 0;
	for(int j = i + 1; j < n-1; j++){
    	if(arr[idx] > arr[j]){
        	int tmp = arr[j];
    		idx = j;
        }
    }
    int tmp = arr[idx];
    arr[idx] = arr[i];
    arr[i] = tmp;
}