선택 정렬 알고리즘 구현 (C++)

가장 먼저 정리할 정렬 알고리즘은 선택 정렬(insertion sort) 알고리즘이다.

이름에서도 알 수 있듯이, 오름차순으로 정렬한다고 하면, 매 수행에서 가장 작은 값을 선택해서 가장 앞으로 보내는 것이다.

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

다음은 특정 배열을 오름차순으로 정렬하는 코드이다.

 
#include <iostream>
#include<algorithm>
using namespace std;
 
int main(){
 
    int a[5] = {1,4,-1,2,6}, idx;
    
    //선택 정렬
    for(int i = 0 ; i < 5 ; i++){
        int Min = a[i];
        for(int j = i+1 ; j < 5 ; j++){
            if(Min > a[j]){
                Min = a[j];
                idx = j;
            }
        }
        swap(a[i], a[idx]);
    }
    
    //결과 출력
    for(int i = 0 ; i < 5 ; i++)
        cout << a[i] << ' ';
    
    return 0;
}