[Algorithm] 정렬 알고리즘 - selectionSort(선택 정렬)

void selectionSort(vector<int> &A){
    for(int i=0;i<A.size();i++){
        int minIdx = i;
        for(int j=i+1;j<A.size();j++){
            if(A[minIdx]>A[j]){
                minIdx = j;
            }
        }        
    swap(i, minIdx, A);
    }
}

각각의 i번째 element에 대해, [i+1, N) 번째 element와 비교하여, 그 중 가장 작은 element와 i번째 element를 교체한다.

 

시간복잡도는 O(N^2)이다. 주어진 배열(혹은 vector나 list)의 element들이 무엇이든 간에 오직 해당 배열의 크기 N만이 시간 복잡도에 관여하므로, 최선/최악의 경우 모두 시간복잡도가 같다.