[c언어] Quick Sort 소스코드

퀵정렬, 퀵소트, Quick sort 를 구현해보았다.

실행화면

소스코드

#include<stdio.h>
#include<stdlib.h>

void shuffle(int *arr);
void swap(int *a, int *b);
void print(int * arr, int st, int ed);
void quick(int *arr);
void partition(int *arr,int _st, int _ed);

int main(int argc, char *argv[])
{
    int arr[16];
    for(int r=0; r<50; r++){
        for(int i=0; i<16; i++){
            arr[i] = i;
        }
     srand(r);
     shuffle(arr);
     printf("%10s : ","shuffle");
     print(arr,0,15);

     quick(arr);
     printf("%10s : ","quick");
     print(arr,0,15);

     printf("=============================================================\n");
     //break;
    }
    system("pause > nul");
    return 0;
}

void quick(int *arr){
    partition(arr,0,15);
}
void partition(int *arr,int _st, int _ed){
    int p = _ed;
    int buf_p = arr[p];
    int st=_st,ed=_ed-1;
    while(st<ed){
        //if(st<p){
        if( arr[st]<arr[p]){
            st++;
            continue;
        }
        if( arr[ed]>arr[p]){
            ed--;
            continue;
        }
        if( arr[st] > arr[ed]){
            swap(arr+st, arr+ed);
        }
    }
    //printf("st=%d,ed=%d,p=%d\n",st,ed,p);
    if( st < p ){
        if( arr[st]>arr[p]){
            swap(arr+st, arr+p);
            int t = p;
            p = st;
            st = t;
        }
    }

    st = _st;
    ed = _ed;
    printf("(%2d)%6s : ",buf_p,"quick");
    print(arr,st,ed);
    if (st < p) 
        partition(arr, st, p-1); 
          if (ed > p) 
              partition(arr, p+1, ed); 
}

void shuffle(int *arr){
    int n = 100;
    int a,b;
    while(n--){
        a = rand()%16;
        b = rand()%16;
        swap(arr+a,arr+b);
    }
}

void swap(int *a, int *b){
    int t = *a;
    *a = *b;
    *b = t;
}

void print(int * arr, int st, int ed){
    for(int i=0; i<16; i++){
        if( st<=i && i<=ed){
            printf("%3d",arr[i]);
        }
        else{
            printf("   ");
        }
    }printf("\n");
}

참고자료
http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC#.EC.95.8C.EA.B3.A0.EB.A6.AC.EC.A6.98