이 테스트를 위해 먼저 0부터 n까지 중복되지 않는 섞여있는 배열을 만들어내는 함수를 작성하였다.
이는 0부터 n까지 배열에 숫자를 삽입 후, 이를 셔플로 섞는 방법으로 구현하였다.
그 코드는 다음과 같다.
//난수 배열 생성기 int myrandom (int i) { return rand()%i;} vector<int> randGenerator(int n){ vector<int> v; srand(time(NULL)); for(int i=0;i<=n;i++){ v.push_back(i); } random_shuffle(v.begin(),v.end(),myrandom); return v; }
입력으로 배열의 크기를 받고, 벡터를 반환한다.
먼저 바로 전 포스트에서 작성한 알고리즘이 정상적으로 작동하는지 확인하겠다.
5개의 정렬이 모두 정상적으로 작동함을 확인 할 수 있었다.
모두 정상적으로 작동하는것을 확인 했으니 이제 모든 정렬의 성능을 테스트 해보도록 하겠다.
이 테스트는 10부터 시작하여 배열 범위를 10배씩 증가시키며 진행하였다.
1. n = 10, n = 100
둘 다 수행 시간이 0으로 측정되었다. 100까지 정도의 범위로는 어떤 정렬을 사용해도 크게 상관 없다는 것을 알 수 있다.
2. n = 10,00
1000개 부터는 속도 차이가 눈에 보이기 시작한다.
선택 정렬, 삽입 정렬, 버블 정렬은 모두 시간 복잡도가 n^2이었다. 그에 따라 셋의 시간이 유사하게 나올줄 알았으나.
삽입 정렬은 삽입 하고자 하는 위치를 찾았을 경우 더이상 비교하지 않으며, 최선의 경우 O(n)에 수행되기 때문에 더 빠른 속도를 보였다.
선택 정렬과 버블 정렬은 둘 다 모든 배열을 비교하는 정렬 알고리즘으로 시간이 유사하게 나옴을 알 수 있다.
그리고 합병 정렬과 퀵 정렬은 둘 다 nlgn에 수행되지만, 앞서 말했다 싶이 퀵 정렬이 조금 더 빠른 성능을 보인다.
3. n = 10,000
각 정렬 별로의 시간은 2번에서 설명한 바와 같다.
그리고 하나 더 알수 있는게, t선택,삽입,버블 정렬의 수행 시간이 이전보다 약 100배정도 증가했다는 사실이다.
이로 시간 복잡도가 O(n^2)이므로 n이 10배 증가하면 100배한다는 것으로 시간 복잡도의 타당성을 알 수 있다.
또한 합병 정렬의 시간복잡도가 nlgn이다. 1000과 10000는 약 13배 정도 차이 나는데 미세한 값으로 변수가 발생하는 부분이 있기 때문에
정확한 증명을 위해서는 더욱 큰 값을 적용할 필요가 있어보인다.
이 와중에도 퀵 정렬은 시간 측정이 안될 정도로 정말 빠른 성능을 보여주었다.
3. n = 100,000
선택,삽입,버블 정렬은 앞과 같다.
합병 정렬은 숫자가 커질수록 nlgn의 증가율과 점점 가까워지고 있음을 확인하였다.
(시간 측정은 어느정도 변수가 있기 때문에 정확한 측정값은 확인하기 힘들었다)
퀵 정렬은 정렬 갯수가 10만이 넘어서야 측정이 되었다.
4. n = 1,000,000
선택,삽입,버블 정렬의 시간이 말도안되게 길어지기 시작했기 때문에 저 셋은 테스트하지 않았다.
사실은 시도는 하였지만 지금까지 측정 시간으로 볼 때 이론상 선택, 버블은 9000초, 삽입은 4000초로 약 2시간 반, 1시간 정도 걸리기 때문에 포기하였다.
5. n = 10,000,000
합병정렬은 유사한 증가율을 보이는데 퀵 정렬은 왜인지 갑자기 30배 가까이 증가했다.
그래도 여전히 합병 정렬보다 빠른 속도를 가지고 있다.
1억개부터는 저 둘로도 마냥 빠르게 측정되지 않기 때문에 여기까지만 테스트하였다.
지금까지 테스트로 퀵 정렬이 상대적으로 높은 성능을 보임을 알 수 있었고, 합병 정렬은 퀵 정렬에 미치지는 못하지만 그래도 나머지 정렬에 비해 상당한 성능임을 확인 할 수 있었다.
또한 버블 정렬과 선택 정렬, 삽입 정렬은 데이터 10만개 이상부터는 실제로 쓰기엔 어려운 성능을 보였다. 그 이하의 데이터에선 합병, 퀵 정렬보단 느리지만 사용해도 크게 무방할것 같다는 생각이 든다.
밑은 이 테스트를 위해 작성한 코드이다.
#include <cstdio> #include <algorithm> #include <vector> #include <ctime> using namespace std; //난수 생성기 int myrandom (int i) { return rand()%i;} vector<int> randGenerator(int n){ vector<int> v; srand(time(NULL)); for(int i=0;i<=n;i++){ v.push_back(i); } random_shuffle(v.begin(),v.end(),myrandom); return v; } //선택 정렬 void selectionSort(vector<int> v){ for(int i=0;i<v.size()-1;i++){ for(int j=i+1;j<v.size();j++) if(v[i]>=v[j]) swap(v[i],v[j]); } // printf("--선택 정렬 결과--\n"); // for(int i = 0; i<v.size();i++) // printf("%d ",v[i]); // printf("\n\n"); } // 삽입 정렬 void insertionSort(vector<int> v){ for(int i=1;i<v.size();i++){ int key = v[i], j = i-1; while(j>=0 && key <v[j]){ swap(v[j], v[j+1]); j--; } v[j+1] = key; } // printf("--삽입 정렬 결과--\n"); // for(int i = 0; i<v.size();i++) // printf("%d ",v[i]); // printf("\n\n"); } //버블 정렬 void bubbleSort(vector<int> v){ for(int i=0;i<v.size()-1;i++){ for(int j=1; j<v.size()-i;j++) if(v[j-1] > v[j]) swap(v[j-1],v[j]); } // printf("--버블 정렬 결과--\n"); // for(int i = 0; i<v.size();i++) // printf("%d ",v[i]); // printf("\n\n"); } //병합 정렬 void merge(vector<int>& v, int s, int e, int m) { vector<int> ret; int i = s, j = m + 1, copy = 0; //결과를 저장할 배열에 하나씩 비교하여 저장한다. while (i <= m && j <= e) { if (v[i] < v[j])ret.push_back(v[i++]); else if (v[i] > v[j])ret.push_back(v[j++]); } //남은 값들을 뒤에 채워넣어준다. while (i <= m) ret.push_back(v[i++]); while (j <= e) ret.push_back(v[j++]); //원래 배열에 복사해준다. for (int k = s; k <= e; k++) { v[k] = ret[copy++]; } } void mergeSort(vector<int>& v, int s, int e){ if(s<e){ int m = (s+e)/2; /*divide, 분할*/ mergeSort(v,s,m);//s부터 m까지 mergeSort(v,m+1,e); //m+1부터 e까지 /*conquer, 병합*/ merge(v,s,e,m); } } //퀵 정렬 void qsort(vector<int>& v, int s, int e) { int pivot = v[s]; int bs = s, be = e; while (s<e) { while (pivot <= v[e]&&s<e) e--; if (s>e) break; while (pivot >= v[s]&&s<e) s++; if (s>e) break; std::swap(v[s], v[e]); } std::swap(v[bs], v[s]); if(bs<s) qsort(v,bs, s-1); if(be>e) qsort(v,s+1, be); } int main(){ clock_t start,end; int n;// 숫자 갯수 printf("랜덤 숫자 범위(1~n) : "); scanf("%d",&n); vector<int> v = randGenerator(n); // printf("정렬 전 : "); // for(int i=0;i<n;i++) // printf("%d ",v[i]); printf("\n\n"); start = clock(); selectionSort(v); end = clock(); printf("선택 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC); start = clock(); insertionSort(v); end = clock(); printf("삽입 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC); start = clock(); bubbleSort(v); end = clock(); printf("버블 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC); vector<int> v2 = v; start = clock(); mergeSort(v2,0,v.size()-1); end = clock(); // printf("--병합 정렬 결과--\n"); // for(int i=0;i<v2.size();i++) // printf("%d ",v2[i]); // printf("\n\n"); printf("병합 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC); start = clock(); qsort(v,0,v.size()-1); end = clock(); // printf("--퀵 정렬 결과--\n"); // for(int i=0;i<v.size();i++) // printf("%d ",v[i]); // printf("\n"); printf("퀵 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC); }
'Algorithm' 카테고리의 다른 글
| 편집 거리 알고리즘(Levenshtein Distance, Edit Distance) (4) | 2016.04.21 |
|---|---|
| 순회하는 외판원 문제(Traveling Salesperson Problem, TSP) (7) | 2016.04.19 |
| 최장 공통 부분 수열(Longest Common Subsequence, LCS) (1) | 2016.04.17 |
| 해쉬 알고리즘(Hash Algorithm) 요약 정리, 테스트 코드 (7) | 2016.04.12 |
| 기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1 (21) | 2016.04.09 |
