퀵 정렬은 분할 해결 전략을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

#define _CRITICIAL_SECTION 0

typedef struct _MATRIX
{
    int **array;
    int col,row;
}MATRIX,Matrix,*pMatrix;

typedef struct _PARAM
{
    MATRIX M1,M2,R;
    int n;
}PARAM,Param,*ptrParam;

int sample1[] = {
    3,4,2,0,4,7,3,0,9,1,2,8,7,4,9,1,
    7,3,8,2,3,1,0,4,5,8,7,3,5,6,8,2,
};
int sample2[] = {
    7,3,8,2,3,1,0,4,5,8,7,3,5,6,8,2,
    3,4,2,0,4,7,3,0,9,1,2,8,7,4,9,1,
};

int n_thread;

#if _CRITICIAL_SECTION
CRITICAL_SECTION cs;
#endif

void assert(bool a){ if(a!=true) {printf("alert!!\n"); exit(0);}/*return ;*/}
void init_matrix(Matrix *, int, int);
int** create_array(int, int);
void set_zero(Matrix *M);
void free_array(int **, int, int);
void mul_matrix(Matrix *, Matrix *, Matrix *);
void mul_matrix_thread(Matrix *, Matrix *, Matrix *);
void cal_part(Matrix *, Matrix *, Matrix *, int);
DWORD WINAPI cal_part_thread(void* arg);
void set_sample(Matrix *, int *);
void print_matrix(Matrix);

int main(int argc, char *argv[])
{
    Matrix M1,M2,Result;

    init_matrix(&M1, 4, 3 );
    init_matrix(&M2, 3, 4 );

    set_sample(&M1, sample1);
    set_sample(&M2, sample2);

    print_matrix(M1);
    print_matrix(M2);

    n_thread = M1.col;

    mul_matrix_thread(&M1,&M2,&Result);

    print_matrix(Result);

    free_array(M1.array, M1.row, M1.col);
    free_array(M2.array, M2.row, M2.col);
    free_array(Result.array, Result.row, Result.col);

    return 0;
}

void init_matrix(Matrix *M,int w,int h)
{
    M->col = h;
    M->row = w;
    M->array = create_array(w,h);
    set_zero(M);
}

int** create_array(int w, int h)
{
    int height=h,width=w;
    int **array = (int **) malloc( sizeof(int *)* height);
    array[0] = (int *) malloc( sizeof(int) * width*height );
    int i;
    for( i=1 ; i< height ; i++)
        array[i] = array[ i-1 ] + width;
    return array;
}

void set_zero(Matrix *M)
{
    memset(M->array[0], 0x00, sizeof(int)*M->col*M->row);
}

void free_array(int **array, int w, int h)
{
    assert(array!=NULL);
    assert(array[0]!=NULL);
    free(array[0]);
    free(array);
}

void mul_matrix(Matrix *M1, Matrix *M2, Matrix *R)
{
    assert(M1->row == M2->col);
    assert(M1->col == M2->row);
    init_matrix(R,M1->col,M2->row);
    int n;
    for( n=0; n < R->col ; n++ ){
        cal_part(M1,M2,R,n);
    }
}

void mul_matrix_thread(Matrix *M1, Matrix *M2, Matrix *R)
{
    PARAM *param=NULL;
    param = (PARAM*)malloc(sizeof(PARAM)*n_thread);
    HANDLE *hThread=NULL;
    hThread = (HANDLE*)malloc(sizeof(HANDLE)*n_thread);

#if _CRITICIAL_SECTION
    InitializeCriticalSection(&cs);
#endif

    assert(M1->row == M2->col);
    assert(M1->col == M2->row);
    init_matrix(R,M1->col,M2->row);
    int i;
    for( i=0; i< n_thread; i++){
        param[i].M1 = *M1;
        param[i].M2 = *M2;
        param[i].R = *R;
        param[i].n = i;
    }
    int n;
    for( n=0; n < R->col ; n++ ){
        hThread[n] = CreateThread(NULL,0,cal_part_thread,(void*)(param+n),0,NULL);
        if(hThread[n]>0){
            printf("hThread[%d] created\n",n);
        }
        else{
            printf("hThread[%d] fail to create\n",n);
        }
    }
    WaitForMultipleObjects(n_thread,hThread,TRUE,INFINITE);

#if _CRITICIAL_SECTION
    DeleteCriticalSection(&cs);
#endif

    for( n=0; n < R->col ; n++){
        CloseHandle(hThread[n]);
    }
    printf("\n");
}

void cal_part(Matrix *M1, Matrix *M2, Matrix *R, int n)
{
    assert(M1->row == M2->col);
    assert(M1->col == M2->row);
    assert(M1->col == R->row);
    assert(M2->row == R->col);
    int buf;
    int i,j;
    for( i=0 ; i < R->row; i++ ){
        for( j=0,buf=0 ; j < M1->row ; j++ ){
            buf += M1->array[n][j]*M2->array[j][i];
        }
        R->array[n][i] = buf;
    }
}

DWORD WINAPI cal_part_thread(void* arg)
{
    PARAM param = *(PARAM *)arg;
    cal_part(&param.M1,&param.M2,&param.R,param.n);
}

void set_sample(Matrix *M, int *src)
{
    assert(M->array!=NULL);
    int i,j;
    for( i=0; i < M->col; i++){
        for( j=0; j < M->row; j++){
            M->array[i][j] = src[i*M->row + j];
        }
    }
}

void print_matrix(Matrix M)
{
    int i,j;
    for( i=0; i < M.col; i++){
        for( j=0; j < M.row; j++){
            printf("%3d ",M.array[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}