3.3.3 퀵 정렬 알고리즘 소스 코드

 //common.h
#pragma once //헤더 파일을 한 번만 포함해서 컴파일
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <memory.h>
#include <time.h>
#pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제

//Book.h
#pragma once
#include "common.h"
#define MAX_TIT_LEN	200
#define MAX_AUT_LEN 20
typedef struct _Book Book;
struct _Book
{
    char title[MAX_TIT_LEN+1];
    char author[MAX_AUT_LEN+1];
    int num;
};

Book *New_Book(const char *title,const char *author,int num);
void Delete_Book(Book *book);
void Book_View(Book *book);
int Book_CompareTitle(Book *book,const char *title);
int Book_CompareAuthor(Book *book,const char *author);
int Book_CompareNum(Book *book,int num);

//Book.c
#include "Book.h"

void Book_Book(Book *book,const char *title,const char *author,int num);
Book *New_Book(const char *title,const char *author,int num)
{
	Book *book = 0;
	book = (Book *)malloc(sizeof(Book));
	Book_Book(book,title,author,num);
	return book;
}
void Book_Book(Book *book,const char *title,const char *author,int num)
{
	memset(book,0,sizeof(Book));
	strncpy(book->title,title,MAX_TIT_LEN);
	strncpy(book->author,author,MAX_AUT_LEN);
	book->num = num;
}
void Delete_Book(Book *book)
{
	free(book);
}
void Book_View(Book *book)
{
	printf("<%010d>:<%s>\n",book->num,book->title);
	printf("\t 저자:%s\n",book->author);
}
int Book_CompareTitle(Book *book,const char *title)
{
	return strcmp(book->title,title);
}
int Book_CompareAuthor(Book *book,const char *author)
{
	return strcmp(book->author,author);
}
int Book_CompareNum(Book *book,int num)
{
	return book->num-num;
}

//Program.c
#include "common.h"
#include "Book.h"
typedef void *Element;
typedef int (*Compare)(Element , Element);               

void quick_sort(Element *base, int n, Compare compare)
{
    Element temp;//교환을 위한 임시 변수
    int pivot = 0; //피벗의 위치를 기억하기 위한 변수
    int big=0, small=0; //피벗보다 큰 값과 작은 값의 위치를 찾기 위한 변수
    if(n<=1)
    {
        return; 
    }//    조건(n<=1)   종료
    //피벗을 선택한다.    
    if(compare(base[0],base[n-1])>0) 
    {
        if(compare(base[0],base[n/2])>0) //base[0]이 제일 큰 값, 이 조건인 거짓일 때는 0번째 원소가 중간 값
        {
            if(compare(base[n/2],base[n-1])>0) //둘 중에 큰 값이 중간 값
            {
                pivot = n/2;
            }
            else
            {
                pivot = n-1;
            }
        }		
    }
    else //base[n-1]이 base[0]보다 크거나 같음
    {
        if(compare(base[n/2],base[n-1])>0)
        {			
            pivot = n-1; //n-1번째 원소가 중간 값
        }
        else//n-1번째 원소가 제일 큰 값
        {
            if(compare(base[n/2],base[0])>0)//이 조건인 거짓일 때는 0번째 원소가 중간 값
            {
                pivot = n/2;//n/2가 중간 값
            }
        }
    }

    //피벗과 맨 앞의 요소를 교환한다.
    temp = base[pivot];
    base[pivot] = base[0];
    base[0] = temp;

    big=0;//big:=0
    small = n;//small:=n
    while(big<small)//반복(big<small)
    {
        for(big++; big<n; big++)//        반복(big:=big+1; big<n; big:=big+1)
        {
            if(compare(base[0],base[big])<0)//            조건(compare(base[0],base[big])<0)
            {
                break;//                루프 탈출
            }
        }
        for(small--; small>0; small--)//        반복(small:small-1;small>0;small:small-1)
        {
            if(compare(base[0],base[small])>0)//            조건(compare(base[0],base[small])>0)
            {
                break;//                루프 탈출
            }			
        }
        if(big<small)//        조건(big<small)
        {
            //            교환(base [big], base [small])
            temp = base[big];
            base[big] = base[small];
            base[small] = temp;
        }
    }
    
    //교환(base [0], base [small])
    temp = base[0];
    base[0] = base[small];
    base[small] = temp;
    quick_sort(base,small,compare);//퀵 정렬(base,small, compare)
    quick_sort(base+big,n-big,compare);//퀵 정렬(base+big, n-big, compare)
}
#define MAX_BOOK	4000
Book *books[MAX_BOOK]={0};
void SimulationInit()
{
    char title[MAX_TIT_LEN+1]="";
    char author[MAX_AUT_LEN+1]="";
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        sprintf(title,"%010d",rand());
        sprintf(author,"%010d",rand());
        books[i] = New_Book(title,author,rand());//랜덤 테스트 용
        //books[i] = New_Book(title,author,i+1); //순차적 테스트 용
    }
}
int CompareByTitle(void *b1,void *b2)
{
    Book *book1=(Book *)b1;
    Book *book2=(Book *)b2;
    return Book_CompareTitle(book1,book2->title);
}
int CompareByNum(void *b1,void *b2)
{
    Book *book1=(Book *)b1;
    Book *book2=(Book *)b2;
    return Book_CompareNum(book1,book2->num);
}

void ListBook(int n)
{
    int i = 0;
    for(i=0; i<n; ++i)
    {
        Book_View(books[i]);
    }
}
void Simulation1()
{
    quick_sort((Element *)books,10,CompareByTitle);
    printf("--------제목순-------\n");
    ListBook(10);
    quick_sort((Element *)books,10,CompareByNum);
    printf("--------번호순-------\n");
    ListBook(10);
}
void Simulation2()
{
    clock_t st,et;
    st = clock();
    quick_sort(books,MAX_BOOK/10,CompareByNum);
    et=clock();
    printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK/10,et-st);
    st = clock();
    quick_sort(books,MAX_BOOK,CompareByNum);
    et=clock();	
    printf("%d개 정렬에 걸린 시간:%d\n",MAX_BOOK,et-st);
}
void SimulationClear()
{
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        Delete_Book(books[i]);
    }
}
int main()
{
    SimulationInit();
    Simulation1();
    Simulation2();
    SimulationClear();
    return 0;
}