퀵정렬 개선하기

입력의 크기가 작을때는 퀵정렬과 삽입정렬의 속도차가 크지 않다.

퀵정렬을 재귀적으로 수행해 나갈 때  크기가 25 보다 작을 때는 더 이상 분할을 중단하고

삽입정렬을 사용하는 코드를 작성하라.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
double toc (double tstart);
#define DTYPE double
#define SWAP(aa,bb) { DTYPE tmp; tmp=aa; aa=bb; bb=tmp;}
DTYPE *mk_rand_data(int N);
void quicksort(DTYPE A[], int left, int right);
void insertionsort(DTYPE A[],int left, int N);
int partition(DTYPE A[], int left, int right);


int main(int argc, char *argv[])
{
        DTYPE *arr, *tmp;
        double tstart;
        int N, i;
        N = atoi(argv[1]);
        srand(clock());
        arr = mk_rand_data( N );
        printf("\n sort .... \n");
        tstart = clock();
        quicksort(arr, 0, N);
        printf("quicksort_insertionsort :%f\n", toc(tstart));
//	for(i=0 ; i < N ; i++)
//	        printf("%f \n", arr[i]);

        return 0;
}

double toc (double tstart)
{
        return (clock() - tstart) / CLOCKS_PER_SEC;
}

DTYPE *mk_rand_data(int N)
{
        DTYPE *arr = (DTYPE *) malloc(sizeof(DTYPE) * N);
        for(int i = 0 ; i < N ; i++)
                arr[i] = rand() / (DTYPE) RAND_MAX;
        return arr;
}
//퀵정렬 추가
void quicksort (DTYPE A[], int left, int right)
{
        int piv;
        if (right - left > 25)
        {
                piv = partition(A, left, right);
                quicksort(A, left, piv);
                quicksort(A, piv + 1, right);
        }
	else
	{
		insertionsort(A, left ,right);
	}
}

int partition(DTYPE A[], int left, int right)
{
        int p = ( left + right ) / 2;
        int i = left, j=right;
        DTYPE pivot;
        SWAP(A[p], A[left]);
        pivot = A[left]; 
        while (1)
        {
                while ( (A[++i] < pivot) && (i < right) );
                while ( (A[--j] > pivot) && (j > left) );
                if (i >= j) break;
                SWAP(A[i], A[j]);
        }
        SWAP(A[left], A[j]);
        return j;
}



void insertionsort(DTYPE A[], int left, int N)
{
        int i, j;
        DTYPE cur_el;
        for(i = left+1 ; i < N ; i++){
                j = i-1;
                cur_el = A[i];
                while ((j >= left) && (A[j] > cur_el)) {
                        A[j+1] = A[j];
                        j --;
                }
                A[j+1] = cur_el;
        }
}

기존의 퀵정렬과 시간 복잡도를 비교하라.

 

N(값)	퀵정렬하다가 25미만이면 선택정렬	퀵정렬
30	0.000005초	0.000007초
50	0.000009초	0.0000014초
1천만	2.24초	2.77초
2천만	4.64초	5.01초
4천만	9.60초	10.24초
8천만	20.04초	20.93초
1억 6천만	41.19초	42.35초

시간복잡도를 비교하면 개선한 것이 약간 더 빠른 것으로 나타납니다.