[정렬] Selection Sort

선택 정렬은 가장 작은 값을 선택해 앞에서부터 정렬하는 방식이다.

다음을 예로 들면,

3

1

4

5

2

우선 3과 뒤의 1, 4, 5, 2 중에서 가장 작은 1을 선택해 3과 교체한다.

1

3

4

5

2

다음, 두 번째 값인 3과 뒤의 4, 5, 2 중 가장 작은 2를 선택해 3과 교체한다.

1

2

4

5

3

세 번째 값인 4와 뒤의 5, 3 중 제일 작은 값인 3을 선택해 4와 교체한다.

1

2

3

5

4

마지막으로, 네 번째 값인 5와 뒤의 4 중 제일 작은 값인 4를 선택해 5와 교체한다.

1

2

3

4

5

오름차순 정렬이 완료된다.

매번 특정 숫자 뒤에서 최솟값을 찾는 과정이 필요하므로 총 시간복잡도는 O(n^2)이다.

버블 정렬은 제일 큰 수 부터 뒤에 정렬하는 과정이었다면, 선택 정렬은 제일 작은 수 부터 앞에 정렬하는 방식이다.

---

#include <iostream>

using namespace std;

int main(void){
    int n = 10;
    int arr[10] = {2, 1, 9, 3, 4, 7, 2, 8, 10, 5};

    for(int i = 0; i < 10; i++){
        // arr[i]와 최솟값 arr[min_idx]을 교체
        int min = arr[i];
        int min_idx = i;
        for(int j = i+1; j < 10; j++){
            if(min > arr[j]){
                min = arr[j];
                min_idx = j;
            }
        }
        arr[min_idx] = arr[i];
        arr[i] = min;
    }

    for(int i = 0; i < 10; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";

    return 0;
}