[Algorithm] 여러가지 정렬 속도 비교(정렬의 시간복잡도)

정렬 속도 비교 

이때까지 포스팅했던 정렬들의 시간복잡도에 대해 알아보도록 하겠습니다.

아래는 정렬속도 비교에 사용하였던 코드입니다.

 

정렬속도 비교 프로그램 (C언어/C++)

출처

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX_SIZE 60000    //데이터의 개수 지정
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))    //SWAP함수 설정
int original[MAX_SIZE];    //랜덤함수로 만든 데이터를 저장할 원본 배열
int list[MAX_SIZE];    //각 정렬 알고리즘에서 사용할 데이터 배열
int n; //데이터의 개수를 받는 전역변수 설정
int sorted[MAX_SIZE]; //합병정렬에서 사용할 데이터를 저장할 배열
clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수
 
//합병정렬
void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i=left, j=mid+1; k=left;
 
    while(i<=mid && j<=right)
    {
        if(list[i]<=list[j])
            sorted[k++]=list[i++];
        else
            sorted[k++]=list[j++];
    }
 
    if(i>mid)
        for(l=j; l<=right; l++)
            sorted[k++]=list[l];
    else
        for(l=i; l<=right; l++)
            sorted[k++]=list[l];
 
    for(l=left; l<=right; l++)
        list[l]=sorted[l];
}
void merge_sort(int list[], int left, int right)
{
    int mid;
    if(left<right)
    {
        mid=(left+right)/2;
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge(list,left,mid,right);
    }
}
 
//퀵정렬
int partition(int list[], int left, int right)
{
    int pivot=list[left], tmp, low=left, high=right+1;
 
    do{
        do
        low++;
        while(low<=right && list[low]<pivot);
 
        do
        high--;
        while(high>=left && list[high]>pivot);
        if(low<high) SWAP(list[low], list[high], tmp);
    }while(low<high);
 
    SWAP(list[left], list[high], tmp);
    return high;
}
void quick_sort(int list[], int left, int right)
{
    if(left<right)
    {
        int q=partition(list, left, right);
        quick_sort(list, left, q-1);
        quick_sort(list, q+1, right);
    }
}

//버블 정렬
void bubble_sort(int list[], int n)
{
    int i, j, tmp;
    printf("버블 정렬 중... ");
    for(i=n-1; i>0; i--)
    {
        for(j=0; j<i; j++)
            if(list[j]>list[j+1])
                SWAP(list[j], list[j+1], tmp);
    }
}
 
//선택 정렬
void selection_sort(int list[], int n)
{
    int i,j,least,tmp;
    
    printf("선택 정렬 중... ");
    for(i=0; i<n-1; i++)
    {
        least=i;
        for(j=i+1; j<n; j++)
            if(list[j]<list[least]) least=j;
        SWAP(list[i], list[least], tmp);
    }
}
 
//삽입 정렬
void insertion_sort(int list[], int n)
{
    int i, j, key;
    printf("삽입 정렬 중... ");
    for(i=1; i<n; i++)
    {
        key=list[i];
        for(j=i-1; j>=0 && list[j]>key; j--)
            list[j+1]=list[j];
        list[j+1]=key;
    }
}
 
//원본 배열을 복사하는 함수
void CopyArr(void)
{
    int i;
    for(i=0; i<n; i++)
        list[i]=original[i];
}
 
//실행 시간을 측정 및 출력하는 함수
void CalcTime(void)
{
    used_time=finish-start;
    printf("완료!\n소요 시간 : %f sec\n\n",(float)used_time/CLOCKS_PER_SEC);
}
 
 
void main ()
{
    int i;
    
    n=MAX_SIZE;
    for(i=0; i<n; i++)
        original[i]=rand();
    
    printf("데이터의 개수 : %d\n\n", n);
 
    CopyArr();
    start=clock();
    selection_sort(list, n);
    finish=clock();
    CalcTime();
    
    CopyArr();
    start=clock();
    insertion_sort(list, n);
    finish=clock();
    CalcTime();
 
    CopyArr();
    start=clock();
    bubble_sort(list, n);
    finish=clock();
    CalcTime();
 
    CopyArr();
    start=clock();
    printf("합병 정렬 중... ");
    merge_sort(list, 0, n);
    finish=clock();
    CalcTime();
 
    CopyArr();
    start=clock();
    printf("퀵 정렬 중... ");
    quick_sort(list, 0, n);
    finish=clock();
    CalcTime();
}

 

결과값

확실히 시간복잡도는 O(N^2)를 가지는 버블정렬, 삽입정렬, 선택정렬보다 

시간복잡도 O(N * LogN)을 가지는 병합정렬, 퀵정렬이 시간면적인 면에서 훨씬 빠른것을 확인할 수 있습니다.

 

정렬 결과 표본 

정렬의 표본을 조사해왔습니다. 엑셀로 표본조사를 했다고 하네요. 참고하실분 참고하시기 바랍니다.

 

[C언어] 버블정렬 (배열에 있는 정수값 오름차순 정렬하기)

[C언어] 선택정렬 (배열에 있는 정수값 내림차순 정렬하기)

[C언어] 삽입정렬 (배열에 있는 알파벳 차례대로 정렬하기)

[C언어] 병합정렬 (실무에서 많이쓰는 정렬방법)

[C언어] 퀵정렬 (가장 빠르고 효율적인 정렬방법)