Selection Sort (선택 정렬)

참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌

알고리즘에 따른 효율성을 가장 잘 보여줄 수 있는 문제가 정렬에 관한 문제이다. 이번에는 시간복잡도는 $O(N^2)$으로 느리지만 가장 단순하게 풀어 볼 수 있는 selection sort(선택정렬)에 대해서 알아본다. Selection sort는 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지는 않다. 

1 10 5 8 7 6 4 3 2 9 의 숫자들이 나열되어 있을 때 이를 오름차순으로 정렬하는 프로그래밍을 작성해보자.

먼저 가장 단순하게 "가장 작은 것을 선택해서 제일 앞으로 보내"는 방법을 생각해보자. 바로 이 방법이 selection sort이다. 한번 손으로 풀어보자.

배열의 처음부터 마지막까지 한번 살펴보자 1이 제일 작은 수 이므로 제일 앞으로 보내면 된다. 이미 제일 앞에 있으므로 정렬이 되었다. 이제 배열의 두번째 부터 마지막까지 또 살펴보면 2가 제일 작은 수 이므로 배열의 두번째 수와 자리를 바꾼다. 다음으로 배열의 세번째부터 마지막까지 살펴보면 3이 제일 작은수 이므로 배열의 세번째 수와 자리를 바꾼다. 이렇게 바꿔가면서 마지막까지 수행하는 방식이 selection sort이다.
1 10 5 8 7 6 4 3 2 9
1 2 5 8 7 6 4 3 10 9
1 2 3 8 7 6 4 5 10 9
.
.
.
이처럼 N(N+1)/2 번의 반복이 되는데 여기서 N 이 무한히 크다고 가정할 경우에 상수의 더하기와 나누기 같은 값들은 무시되기 떄문에 시간 복잡도는 $O((N^2+N)/2)$가 아닌 $O(N^2)$이 된다.

이제 이를 c++로 구현해보자

/******************************************************************************
1. 배열 속에서 제일 작은 인덱스를 찾고
2. 그 작은 인덱스의 값과 배열의 첫번째 값을 교체 한다.
3. 배열의 시작을 하나씩 오른쪽으로 옮기면서 같은 동작을 반복 한다.
*******************************************************************************/
#include <iostream>
#include <vector>
using namespace std;

void selection_sort(vector<int> *data){
    
    for(int i=0; i<data->size(); i++){
        int temp = 0;
        int min = numeric_limits<int>::max();
        int idx = 0;        
        //배열 속에서 제일 작은 인덱스를 찾고
        for(int j=i; j<data->size(); j++){
            if(data->at(j) < min){
                min = data->at(j);
                idx = j;
            }
        }        
        //작은 인덱스의 값과 배열의 첫번째 값을 교체 한다.
        temp = data->at(idx);
        data->at(idx) = data->at(i);
        data->at(i) = temp;
    }//배열의 시작을 하나씩 오른쪽으로 옮기면서 같은 동작 반복
}

int main(){
    int array_size = 10, inputs;
    
    std::vector<int> sort_array;
    
    for(int i=0; i<array_size; i++){
        cin >>inputs;
        sort_array.push_back(inputs) ;
    }
	//sort_array의 주소값을 함수의 인자로 넣어서
	//정렬이 끝난 후 main()의 sort_array또한 정렬된 상태가 되도록 한다.
	//그렇지 않을 경우는 selection_sort의 return값을
	//vector<int>의 정렬된 함수를 return하도록 하고
	//이 return값을 main()에서 받아주는 방식으로 할 수 있음
    selection_sort(&sort_array);
    
    for(int i=0; i<array_size; i++){
        cout << sort_array.at(i) << " ";
    }
    return 0;
}

동일한 방식의 코드로 백준2750 을 푼 결과는 다음과 같다.

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

void selectionSort(vector<int> *data, int size){
    int i, j, idx, temp, min;
    for(i=0; i<size; i++){        
        min = 1001;
        for(j=i; j<size; j++){
            if(data->at(j) < min){
                min = data->at(j);
                idx = j;
            }
        }
        temp = data->at(idx);
        data->at(idx) = data->at(i);
        data->at(i) = temp;
    }
}

int main(){
    int a,b;
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >>a;
    vector<int> inputs;
    for(int i=0; i<a; i++){
        cin >> b;
        inputs.emplace_back(b);
    }
    //매체점마다 정렬해야할 숫자들의 갯수가 달라지므로 그에 맞게 vector size를 맞춰준다
    //메모리 관리 차원...
    inputs.shrink_to_fit();
    selectionSort(&inputs, a);
    for(int i=0; i<a; i++){
        cout << inputs.at(i) << endl;
    }
    
}

수행시간은 40ms로 느린편이다.