Sort Algorithm Compare

• 시험 방법
  정렬 알고리즘들을 500~550개(랜덤)의 값을 만들어 정렬하는 것을 5000번 반복한 시간을 측정하였다.

qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
4029 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
3190 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
2257 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
361 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
236 ms

• 랜덤한 값들을 정렬할 경우 알고리즘별로 시간 측정 결과 대략적으로 다음과 같은 순서로 성능이 좋았다. 퀵소트 이름이 괜히 퀵이 아니다.
• quick > merge > insertion > bubble > selection
• 위 결과는 정렬할 대상의 상태(값 배열)에 따라 달라질 수 있다.

#include <iostream>
#include <vector>
#include <ctime>
#include <chrono>

void selection_sort(int arr[], int size) {
    for(int i = 0 ; i < size - 1 ; i++) 
        for (int j = i + 1 ; j < size ; j++) 
            if(arr[i] > arr[j]) {
                // swap(arr[i], arr[j]);
                int t = arr[i] ;
                arr[i] = arr[j] ;
                arr[j] = t ;
            }
}


void bubble_sort(int a[], int n){
    int i, j, t;
    for (i = 0; i < n - 1; i++) {
        int bchanged=0 ;
        for (j = 1; j < n - i; j++) // j=(1,10)
        {
            if (a[j - 1] > a[j]){
                t = a[j - 1];
                a[j - 1] = a[j];
                a[j] = t;
                bchanged=1 ;
            }
        }
        if (bchanged==0) break ;
    }
}


void insertion_sort(int arr[], int size) {
    for(int i = 1 ; i <= size - 1 ; i++) 
        for (int j = i-1 ; j >= 0 ; j--) 
            if(arr[j] > arr[j+1]) {
                // swap(arr[j], arr[j+1]);
                int t = arr[j] ;
                arr[j] = arr[j+1] ;
                arr[j+1] = t ;
            } 
            else
                continue;
} 



void merge_sort(int arr[], int size) {
    // std::cout << "merge_sort size=" << size << std::endl ;

    if (size > 2) {
        // 왼쪽 반, 오른쪽 반을 나누어 반복.
        merge_sort(arr, size / 2);
        merge_sort(arr + size / 2, size - size / 2);
        
        // 왼쪽, 오른쪽 반이 각각 정렬된 상태임. merge한다.
        int leftCursor = 0;
        int rightCursor = size / 2;
        //int buff[50];
        int *buff = new int[size] ;

        int buffCursor = 0;
        // 두 그룹을 각각 스캐닝하면서 순서대로 기록. (어느 한쪽이 끝날때까지)
        while (leftCursor < size / 2 && rightCursor < size) {
            if (arr[leftCursor] < arr[rightCursor]) {
                buff[buffCursor++] = arr[leftCursor++];
            } else {
                buff[buffCursor++] = arr[rightCursor++];
            }
        }
        // 남은 한 그룹의 데이터를 append 
        for (int i = leftCursor ; i < size / 2 ; i++)
            buff[buffCursor++] = arr[i];
        for (int j = rightCursor ; j < size ; j++) 
            buff[buffCursor++] = arr[j];
        memcpy(arr, buff, size * sizeof(int));
        delete[] buff ;
    } else { // 원소 개수가 2개 이하인 경우, 비교하여 정렬한다.
        if (arr[0] > arr[1]) {
            // swap(arr[0], arr[1]);
            int tmp = arr[0] ;
            arr[0] = arr[1] ;
            arr[1] = tmp ;
        }
    }
}



// a: 정렬할 데이터 array
// n: 데이터 개수
void quick_sort(int a[], int n){
	int v, t;
	int i, j;
	if (n > 1){
		v = a[n - 1]; // v=축값. 마지막 노드값을 사용
		i = -1; 
		j = n - 1; 
		while (1){ // 분할
			// while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지? -> 없다면??? 없을수는 없다. 자신끼리 비교가 마지막.
            while (a[++i]<v) {
                // std::cout << "debug : i=" << i << std::endl ; 
            }

			// while (a[--j] > v); // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range???
            while( a[--j]>v) {
                // std::cout << "debug : j=" << j << std::endl ; 
                // minus index로 갔는데 에러가 발생하지 않았지만, 쓸데없는 오버로드다. 다른 언어였으면 indexerror이다. 
                if (j==0)   // 전체 검색 완료이므로 더 이상 할 필요없다.
                    break ;
            }
			if (i >= j) 
                break; // i와 j의 위치가 뒤바뀌었으면 분할 끝. 좌우 분할이 이미 잘되어 있다. 
            // i와 j의 위치가 좌, 우 상태 그대로 라면 
			t = a[i]; // 두 값을 바꿈. 
			a[i] = a[j];
			a[j] = t;
		}
        // 피봇이 들어갈 자리는? 왼쪽을 기준으로 정렬이 다 된 상태에서 마지막 i자리에 큰 값이 와 있다. 
		t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
		a[i] = a[n - 1];
		a[n - 1] = t;
        // i위치 기준으로 좌우 대소 분할 완료.
		quick_sort(a, i); // 왼쪽 구간 퀵정렬. (i개만 한다. 즉, i위치는 개수에 포함 안함.)
		quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬 (index로 치면 a+i+1부터 a+n-1. 따라서 개수는 a+n-1 - (a+i+1)+1 )
	}
}



void print_array(int *a, int n) {
    for(int i=0; i<n; i++)
    {
        std::cout << a[i] << " " ;
    }
    std::cout << std::endl ;
}

int check_asc(int *a, int n) {
    if (n<=1) return 1 ;
    for (int i=1; i<n; i++) {
        if (a[i-1]>a[i])
            return 0 ;
    }
    return 1 ;
}

int test_alg(void (*pfunc)(int[], int)) {
    int cnt = std::rand()%50+500 ;
    int *a = new int[cnt] ;
    int bcheck=0 ;

    if (true) {
        // 랜덤값 생성
        for (int i=0; i<cnt; i++) {
            a[i]=  std::rand()%1000 ;
        }
    } else {
        // 이미 정렬된 상태값 생성
        for (int i=0; i<cnt; i++) {
            a[i]=  i ;
        }
    }

    // print_array(a,cnt) ; // 정렬 전.
    // (*pfunc)(a, cnt) ;   // 이렇게 해도 가능.
    pfunc(a,cnt) ;
    // print_array(a,cnt) ; // 정렬 후.
    bcheck = check_asc(a,cnt) ;

    delete[] a ;
    return bcheck ;
}


uint64_t getmilli() {
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count() ;
}


int main() {

    std::cout << "sort test" << std::endl ;
    std::srand(std::time(NULL)) ;

    // int a[] = {3,8,5,1,9,4,2,6,7, 10} ;
    // int a[10] ;
    // for (int i=0; i<10; i++) {
    //     a[i] = std::rand()%50 ;
    // }
    // int n = sizeof(a)/sizeof(int) ;
    // print_array(a, n) ;
    // quick_sort(a, n) ;
    // merge_sort(a, n) ;
    // bubble_sort(a, n) ;
    // print_array(a, n) ;
    // return 0 ;

    int bcheck=0 ;
    int okcnt = 0, failcnt=0 ;
    uint64_t ts, te ;


    const char *pfunc_name[] = { "selection_sort",  "bubble_sort", "insertion_sort", "merge_sort",  "quick_sort",   NULL} ;
    void(*pfunc[])(int[], int) = { selection_sort, bubble_sort, insertion_sort, merge_sort, quick_sort,  NULL };
    int pfunc_cnt = sizeof(pfunc) / sizeof(pfunc[0]) ;

    for (int kk=0; kk<pfunc_cnt; kk++) {
        okcnt=0 ;
        failcnt=0 ;
        if (pfunc[kk]==NULL)
            break ;
        std::cout << "ALG=" << pfunc_name[kk] << std::endl ;

        ts = getmilli() ;
        for (int i=0; i<5000; i++) {
            bcheck = test_alg(pfunc[kk]) ;
            if (bcheck) {
                okcnt++ ;
                // std::cout << "OK" << std::endl ;
            } else {
                failcnt++ ;
                // std::cout << "FAIL" << std::endl ;
            }
        }
        te = getmilli() ;
        std::cout << "OK cnt=" << okcnt << "  FAIL cnt=" << failcnt << std::endl ;
        std::cout << te-ts << " ms" << std::endl ;
    }

    return 0 ;
}

만약 이미 정렬된 상태를 다시 정렬을 시키면?

qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
1507 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
16 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
1439 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
164 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
1329 ms

• 위 경우, bubble, merge가 성능이 좋았다. bubble이 좋았던 이유는 바로 이미 정렬되어 있는지를 처음 루프에서 알아낼 수 있기 때문에 그 조건으로 루프 탈출이 가능하기 때문이다.
• 위 조건은 quick 소트 입장에서는 worst case이다. 먼저 이미 정렬되었는지 검사하는 루틴을 추가한다면 이런 경우를 방지할 수 있을 것이다.

Author: crazyj7@gmail.com