기본 정렬 알고리즘(Sorting Algoritm) 성능 비교

이 테스트를 위해 먼저 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);
    
}