참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌
알고리즘에 따른 효율성을 가장 잘 보여줄 수 있는 문제가 정렬에 관한 문제이다. 이번에는 시간복잡도는 $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로 느린편이다.
'Programming > Algorithm' 카테고리의 다른 글
Merge Sort (병합 정렬) (0) | 2021.09.28 |
---|---|
Quick Sort (퀵 정렬) (0) | 2021.09.15 |
댓글