선택정렬(Selection Sort)

1. 주어진 수열 중 최소값의 인덱스를 찾는다.
   
2. 최소값의 인덱스를 맨 앞에 위치한 값과 교체한다.
3. 이 과정을 마지막 인덱스 바로 전까지 진행한다.

시간복잡도는 O(N^2) 이다. 

참고 : https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

[C++11 source code]

#include<iostream>
#include<vector>
using namespace std;
 
void print_v(vector<int>& v) {
    for (auto it : v) {
        printf("%d ", it);
    }
    puts("");
}
 
int main() {
    int n;
    vector<int> v;
    cin >> n;
    v = vector<int>(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    } // input
    
    for (int pivot = 0; pivot < n - 1; pivot++) {
        int change_index = pivot;
        
        for (int there = pivot + 1; there < n; there++) {
            if (v[change_index] > v[there]) {
                change_index = there;
            }
        }
 
        if (change_index == pivot) continue;
        int temp = v[pivot];
        v[pivot] = v[change_index];
        v[change_index] = temp;
    } // selection sort
 
    print_v(v);
 
    return 0;
}
/*
input format
N ~ # of numbers
v[0] ... v[N-1]
*/