[정렬] 선택 정렬

작성일 | In

작동 방식

버블 정렬은 인접한 두 수를 비교해서 정렬을 했습니다.
반면, 선택 정렬은 최소값을 선택해 맨 앞으로 옮겨주는 방법으로 정렬을 합니다.

2 5 3 1 4 7 6 을 선택정렬을 이용해 정렬해봅시다.
슬래시 앞쪽은 정렬이 완료된 상태이고, “” 안에 있는 숫자는 최소값으로 선택된 원소입니다.

1
2
3
4
5
/ 2 5 3 "1" 4 7 6
1/ 5 3 "2" 4 7 6
1 2 3/ 5 "4" 7 6
1 2 3 4 5/ 7 "6"
1 2 3 4 5 6 7 /

이러한 과정을 거쳐 정렬이 됩니다.
또한, 잘 관찰해보면 뒤부터 정렬되는 버블정렬과 달리, 앞부터 정렬이 됩니다.

구현

1
2
3
4
5
6
7
8
9
for(int i=0; i<n; i++){
    int indexMin = i;
    for(int j=i+1; j<n; j++){
        if(arr[j] < arr[indexMin]) indexMin = j;
    }
    int tmp = arr[i];
    arr[i] = arr[indexMin];
    arr[indexMin] = tmp;
}

최소값의 인덱스를 indexMin에 저장한 뒤, 현재 데이터와 indexMin에 있는 데이터를 swap하면서 정렬을 합니다.

시간 복잡도 분석

선택 정렬의 시간 복잡도를 분석해봅시다.
첫 번째 for문이 1부터 n까지, 두 번째 for문은 n-i-1번, 즉 (n-1, n-2, n-3, … , 1)번 돕니다.
1부터 n-1까지 모두 더하면 n*(n-1)/2 = (n2 - n) / 2 ∈ O(n2) 입니다.