Improving the Perfromance of Quick Sort

Insertion Sort

void insert_sort(int *A, int n){
    int i,j,tmp;
    
    for(i =1;i<n;i++){
        tmp=A[i];
        j=i;
        while((j>0)&&(tmp<A[j-1])){
            A[j]=A[j-1];
            j--;
        }
        A[j]=tmp;
    }
}

앞으로 하나씩 비교하면서 자신보다 작은 것을 찾으면 그 뒤에 들어가고 종료한다.

insertion sort worst case

insertion average case

---

Selection Sort

앞에서 부터 남은 뒤에 것들과 비교하여 최솟값을 찾고 그 최솟값과 자리를 바꿔준다.

void selection_sort(int *A,int n){
    int i,j,cur;
    for(i =0;i<n-1;i++){
        cur=i;
        for(j=i+1;j<n;j++){
            if(A[cur]>A[j])
                cur=j;
        }
        SWAP(A[i],A[cur]);
    }
}

Selection sort는 중간에 멈추는 조건이 없기 때문에 worst case와 average case의 시간 복잡도가 같다.

Selection sort와 insertion sort 시간복잡도 비교

---

Improving the Perfromance of Quick Sort

Quick Sort의 속도를 향상시키는 법이 있을까?

void i_quicksort(int a[],int l, int r){
    int i,pivot;
    if(r-l+1<=M) return;
    exch(&a[(l+r)/2],&a[r-1]);
    
    //아래 식을 통하여 a[l]<a[r-1]<a[r]이 만들어진다.
    compexch(&a[l],&a[r-1]);
    compexch(&a[l],&a[r]);
    compexch(&a[r-1],&a[r]);
    
    pivot=partition(a,l+1,r-1);
    
    i_quicksort(a,l,pivot-1);
    i_quicksort(a,pivot+1,r);
    
}

일단 위처럼 quick sort를 변형한다.

그렇게 되면 l<(l+r)/2<r이 되게 되는데 이렇게 되면 훨씬 더 좋은 pivot을 얻을 수 있고 tree의 depth를 줄여서 재귀가 돌아가는 것을 방지  할 수 있다.

또, if(r-l+1<=M) return; 를 넣어서 M보다 작은 경우는 재귀를 돌지 않게 하였다.

그렇다면 이 정렬되지 않은 M은 어떻게 처리 할 것인가??

quick정렬이 끝나면 바로 insertion sort를 통해 정렬 되지 않은 부분을 정렬해준다.

quick정렬을 통해 배열이 거의 정렬된 배열이 되었으므로 insertion sort의 시간복잡도는 거의 O(n)이 된다.

 

 

insertion&quicksort와 기존 quicksort의 시간차이

T는 변형된 quick정렬이 돌고난 후에 insertion sort가 반복문을 몇번 돌았는지 보여주고 있다.

1000개의 data를 받았는데 고작 1224번의 반복문 밖에 돌지 않았다. 시간복잡도가 O(n)이라는 것을 알 수 있다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define M 10
#define size 1000
int T;

void exch(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void compexch(int* x, int* y)
{
    if (*x > *y){
        int temp = *x;
        *x = *y;
        *y = temp;
    }
}

int partition(int *a,int l, int r){
    int pivot,i;
    pivot=l;
    for(i=l;i<r;i++){
        //i와 r을 비교해서 r이 더 크다면 i와 pivot을 바꾸고 pivot++을 해라
        if(a[i]<a[r]){
            exch(&a[i],&a[pivot]);
            pivot++;
        }
    }
    exch(&a[pivot],&a[r]);
    return pivot;
}

void i_quicksort(int a[],int l, int r){
    int i,pivot;
    if(r-l+1<=M) return;
    exch(&a[(l+r)/2],&a[r-1]);
    
    //아래 식을 통하여 a[l]<a[r-1]<a[r]이 만들어진다.
    compexch(&a[l],&a[r-1]);
    compexch(&a[l],&a[r]);
    compexch(&a[r-1],&a[r]);
    
    pivot=partition(a,l+1,r-1);
    
    i_quicksort(a,l,pivot-1);
    i_quicksort(a,pivot+1,r);
    
}

void quick_sort(int *n, int left, int right){
    int pivot;
    
    if(right-left>0){
        //divide
        pivot=partition(n,left,right);
        
        //conquer
        quick_sort(n,left,pivot-1);
        quick_sort(n,pivot+1,right);
    }
}

void insertion(int a[]){
    int temp,i,j;
    for(i=1;i<size;i++){
        temp=a[i];
        j=i;
        while((j>0)&&(temp<a[j-1])){ //j-1주의
            T++;
            a[j]=a[j-1];
            j--;
        }
        a[j]=temp;
    }
}

void setArray(int a[], int n)
{
    for (int i = 0; i < n; i++) {
        a[i] = rand() % n;
    }
}

void printArray(int a[]){
    for(int i=0;i<size;i++) printf("%d ",a[i]);
}

void sort(int a[], int l, int r)
{
    i_quicksort(a, l, r);
    //printf("\n\n----quicksort----\n");
    //printArray(a);
    insertion(a);
    //printf("\n\n----insertion----\n");
    //printArray(a);
    printf("\nT : %d\n",T);
}

int main()
{
    srand(time(NULL));
    clock_t start1,start2,end1,end2;

    T=0;
    int *A = (int *)malloc(sizeof(int)*size);
    int *B = (int *)malloc(sizeof(int)*size);
    setArray(A,size);
    B=A;
    printf("\n----Array----\n");
   
    start1 = clock();
    sort(A, 0, size-1);
    end1 = clock();
    printf("insert quicksort time : %f\n",(float)(end1 - start1)/CLOCKS_PER_SEC);
    start2=clock();
    quick_sort(B,0,size);
    end2=clock();
    printf("quicksort time : %f\n",(float)(end2 - start2)/CLOCKS_PER_SEC);

    return 0;
}

 

---

quickSort는 어쩔 수 없이 depth가 unbalance하게 늘어날 수 밖에 없고, 이는 stack overflow가 나게 할 수 있다.

void quickSortTRO(int a[], int l, int r)
{
    if (r - l == 1) {
        compexch(&a[l], &a[r]);
        return;
    }
    int l1, r1, l2, r2;
    int splitPoint;

    l2 = l, r2 = r;
    while (r2 - l2 > 1) { // 최소 3개 이상은 되어야 pivot을 잡을 수 있음
        splitPoint = partition(a, l2, r2);
        if (splitPoint < (l2 + r2) / 2) {
            l1 = l2, r1 = splitPoint - 1; // 더 작은 영역에 대해 recursive call 한다
            l2 = splitPoint + 1, r2 = r2;
        }
        else {
            l1 = splitPoint + 1, r1 = r2;
            l2 = l2, r2 = splitPoint - 1;
        }
        quickSortTRO(a, l1, r1);
    }
}

위와 같이 코드를 짜면 pivot으로 나누어진것 중에 작은 것을 먼저 선택하므로 tree의 최대 depth는 logN을 넘지않아 stackoverflow를 막을 수 있다.