자료구조 :: 정렬(5) 정렬 함수 시뮬레이션

# 정렬 함수

SortLibrary.cpp

지금까지 배운 정렬 함수들을 종합했다.
경과 시간을 볼 수 있는 부분을 추가했지만 10000개 이상의 데이터가 아닌 이상 1초도 걸리지 않는다.
콘솔 창에 출력이 일어나기때문에 출력 전에 시간을 표시했지만 10000개의 데이터의 경우 출력이 너무
많아져서 스크롤이 넘어가버린다. 출력은 파일에다가 하고 경과 시간만 표시해주면 될 것 같다.

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

#define random(n) (rand()%n) // 랜덤값 매크로
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) // 교환 매크로

typedefstruct QueueNode { 
int item; 
    QueueNode *link; 
}QueueNode; 

typedefstruct { 
    QueueNode *front, *rear; 
}QueueType; 

void SelectSort(int *list, int n); // 선택 정렬
void InsertSort(int *list, int n);    // 삽입 정렬
void BubbleSort(int *list, int n);    // 버블 정렬
void ShellSort(int *list, int n);     // 쉘 정렬
void ShakerSort(int *list, int n);    // 쉐이커 정렬
void QuickSort(int *list, int left, int right); // 퀵 정렬
void RadixSort(int *list, int n);     // 기수 정렬

// 기수 정렬을 위한 큐 함수
void Init(QueueType *q); 
int is_empty(QueueType *q); 
void Enqueue(QueueType *q, int item); 
int Dequeue(QueueType *q); 

// 출력 함수
void ScreenOut(int *pList, int count); 

void TimeAttack(int tm) 
{         

} 

int main() 
{ 
int i,input,choice,tm; 
int *list; 
char *msg; 

    srand((unsignedint)time(NULL)); 

    printf("Input Data Count : "); 
    scanf("%d",&input); 

    list=(int *)malloc(sizeof(int)*input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("\n-------------------------------\n"); 
    printf("Insert Data list .... "); 
    printf("\n-------------------------------\n\n"); 
    ScreenOut(list,input); 

    printf("\n-------------------------------\n"); 
    printf("Select Sorting Method .... "); 
    printf("\n-------------------------------\n\n"); 
    printf("1.선택 정렬\n2.삽입 정렬\n3.버블 정렬\n4.쉘   정렬\n5.쉐이커 정렬\ 
           \n6.퀵   정렬\n7.기수 정렬\n8.종     료\n"); 
    printf("Select Number : "); 
    scanf("%d",&choice); 

    tm=GetTickCount(); 

switch(choice) 
    {     
case1:    SelectSort(list,input); msg="Select"; 
break; 
case2:    InsertSort(list,input); msg="Insert"; 
break; 
case3: BubbleSort(list,input); msg="Bubble"; 
break;  
case4: ShellSort(list,input); msg="Shell"; 
break; 
case5: ShakerSort(list,input); msg="Shaker"; 
break; 
case6: QuickSort(list,0,input-1); msg="Quick"; 
break; 
case7: RadixSort(list,input); msg="Radix"; 
break; 
default : 
return0; 
    } 

    printf("정렬 시간 : %.3f초\n",(GetTickCount()-tm)/1000.0); 

    printf("\n%s Sorting Data : ",msg); 
    ScreenOut(list,input); 

    free(list); 

return0; 
} 

void SelectSort(int *list, int n) 
{ 
int i,j,temp,least; 

for(i=0;i<n-1;i++)  
    { 
        least=i; // list[i]를 최소값으로 함

for(j=i+1;j<n;j++) 
        { 
if(list[least]>list[j]) 
                least=j; // 기준값보다 작은값으로 인덱스 변경
        } 

if(least != i) // 최소값 변경이 없으면 SWAP하지 않는다
            SWAP(list[i],list[least],temp); 
    }     
} 

void InsertSort(int *list, int n) 
{ 
int i,j,item; 

for(i=1;i<n;i++) 
    { 
        item=list[i]; // list[i]를 기준값으로 함

for(j=i-1;j>=0;j--) // j는 기준을 제외하고 0보다 크거나 같을때까지
        { 
if(list[j] > item) // 정렬이 된 곳 중에서 item보다 작은값을 찾음
                list[j+1]=list[j]; 
else
break;  
        } 
        list[j+1]=item; // 작은값을 찾은 자리에 대입
    } 
} 

void BubbleSort(int *list, int n) 
{ 
int i,j,temp,flag; 

for(i=n-1;i>0;i--) 
    { 
        flag=0; 
for(j=0;j<i;j++) 
        { 
if(list[j] > list[j+1]) 
            { 
                SWAP(list[j],list[j+1],temp); 
                flag=1; 
            } 
        } 
if(!flag) // 전체 배열의 데이터 변경이 없다면 종료 
break; 
    } 
} 

void ShellSort(int *list, int n) 
{ 
int i,j,temp,gap; 

for(gap=1;gap<n/3;gap=3*gap+1); // 최적의 간격을 찾는다

while(gap > 0) 
    { 
for(i=gap;i<n;i++) // gap을 간격으로 하여 삽입정렬
        { 
for(j=i-gap;j>=0;j=j-gap) 
            { 
if(list[j]>list[j+gap]) 
                    SWAP(list[j],list[j+gap],temp); 
else
break; 
            } 
        } 
        gap/=3; // 간격을 줄인다 
    } 
} 

void ShakerSort(int *list, int n) 
{ 
int i,temp; 
int left,right,shift; 

    left=0; 
    right=n-1; 

while(left<right) 
    { 
for(i=left;i<right;i++) 
        { 
if(list[i]>list[i+1]) 
            { 
                SWAP(list[i],list[i+1],temp); 
                shift=i; // 마지막으로 교환이 발생한 인덱스 저장
            } 
        } 
        right=shift; // 마지막 교환 인덱스 값을 right값에 대입

for(i=right;i>left;i--) 
        { 
if(list[i]<list[i-1]) 
            { 
                SWAP(list[i],list[i-1],temp); 
                shift=i; // 마지막으로 교환이 발생한 인덱스 저장
            } 
        } 
        left=shift; // 마지막 교환 인덱스 값을 left값에 대입
    } 
} 

void QuickSort(int *list, int left, int right) 
{ 
int i,j,pivot,temp; 

if(left<right) 
    { 
        i=left; 
        j=right+1; 

        pivot=list[left]; // pivot은 리스트의 첫번째 값

do{ 
while(list[++i] < pivot); // left부터 pivot값보다 작은값을 찾는다
while(list[--j] > pivot); // right부터 pivot값보다 작은값을 찾는다

if(i < j) 
                SWAP(list[i],list[j],temp); // 위에서 찾아낸 인덱스끼리 교환
        }while(i < j); 

        SWAP(list[left],list[j],temp); // pivot의 자리를 변경

// pivot을 기준으로 반으로 나누고 각각을 재귀 호출로 반복 정렬 한다
        QuickSort(list,left,j-1);  
        QuickSort(list,j+1,right);         
    } 
} 

void Init(QueueType *q) 
{ 
    q->front=q->rear=NULL; 
} 

int is_empty(QueueType *q) 
{ 
return (q->front==NULL); 
} 

void Enqueue(QueueType *q, int item) 
{ 
    QueueNode *temp=(QueueNode*)malloc(sizeof(QueueNode)); 

    temp->item=item; 
    temp->link=NULL; 

if(is_empty(q)) 
    { 
        q->front=temp; 
        q->rear=temp; 
    } 
else
    { 
        q->rear->link=temp; 
        q->rear=temp; 
    } 
} 

int Dequeue(QueueType *q) 
{ 
    QueueNode *temp = q->front; 
int item; 

if(is_empty(q)) 
    { 
        printf("큐가 비어있습니다\n"); 
return -1; 
    } 

    item=temp->item; 
    q->front=q->front->link; 

if(q->front==NULL) 
        q->rear=NULL; 

    free(temp); 

return item; 
} 

void RadixSort(int *list, int n) 
{ 
constint BUCKETS=10; // 10진법
constint DIGITS=2;   // 숫자의 자릿수 
int i,j,k; 
int factor=1; // 증가량 1,10,100,...
    QueueType queue[BUCKETS]; 

for(i=0;i<BUCKETS;i++) 
        Init(&queue[i]); // 큐 초기화

for(k=0;k<DIGITS;k++) 
    { 
for(i=0;i<n;i++) 
            Enqueue(&queue[(list[i]/factor)%10],list[i]); // 자리수에 따라 큐에 삽입

for(i=j=0;i<BUCKETS;i++)  
        { 
while(!is_empty(&queue[i])) // 모든 큐가 NULL 일때 까지
                list[j++]=Dequeue(&queue[i]); // 정렬된 데이터 삽입
        } 
        factor*=10; // 다음 자릿수로 변경
    } 
} 

void ScreenOut(int *pList, int count) 
{ 
int i; 
for(i=0;i<count;i++) 
        printf("%d ",pList[i]); 

    puts(""); 
}