DS_HW2

#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAX_SIZE 10000000
#define SWAP(x,y,t)((t)=(x), (x)=(y), (y)=(t))
#define MALLOC(p,s) \
        if(!((p) = malloc(s))) {\
        fprintf(stderr , "Insufficient memory"); \
        exit(0);\
        }
/* Sort functions decalaration */
/* Quick Sort */
void QuickSort(int a[],int left,int right);

/* Merge Sort */
void mergesort_new(int list[], int temp[],int left, int right);
/*
int listMerge(int a[], int link[], int start1, int start2);
int reMergeSort(int a[],int link[], int left, int right);
void Merge(int initlist[], int mergedlist[], int head, int middle, int tail);
void MergePass(int initlist[], int mergedlist[], int n, int size);
void MergeSort(int a[],int n);
*/
/* Heap Sort */
void Heap_Construct(int list[],int n);
void Heap_Adjust(int list[],int n,int i);
void Heap_Sort(int list[],int n);

/* Others */

void printAry(int a[],int left, int length);
void Intro(void);

int main(int argc, const char * argv[])
{
    /* Variable decalre */
    int Data_input , Data_num , Sort_way;
    int *Data_ary,*temp;
    int i;
    clock_t start_time, end_time;

    while(1)
    {
        Intro();

        /* Way to input data */
        printf("Please decide how to input data\n");
        printf("1. Enter by yourself\n");
        printf("2. Generate in random\n");
        printf("0. Exiting the program\n");
        scanf("%d",&Data_input);
        if(!(Data_input != 1 || Data_input != 2))
        {
          printf("Please key in 1 or 2 !!\n");
          exit(0);
        }
        else if(Data_input == 0)  break;

        printf("\n");      //puts("\n");

        /* Number of datas */
        printf("Please decide how many datas you need\n");
        printf("0<n<%d\n",MAX_SIZE);
        scanf("%d",&Data_num);
        if(!(Data_num >0 && Data_num < MAX_SIZE))
        {
          printf("Exceed the limited range!!\n");
          exit(0);
        }

        printf("\n");      //puts("\n");
        MALLOC(Data_ary,Data_num * sizeof(int));

        /* Setting data array */
        switch(Data_input)
        {
                          case 1:
                               printf("Please input the data you need\n");
                               for(i=0; i<Data_num; i++)
                                        scanf("%d",&Data_ary[i]);
                               break;
                          case 2:
                               printf("Auto generate datas...\n");
                               srand(time(NULL));
                               for(i=0; i<Data_num; i++)
                                        Data_ary[i] = rand();
                               break;
        }
        printAry(Data_ary , 0, Data_num);

        /* Sorting way */
        printf("Now,how to sort?\n");
        printf("1.Quick Sort\n");
        printf("2.Merge Sort\n");
        printf("3.Heap  Sort\n");
        scanf("%d",&Sort_way);
        if(!(Sort_way >0 && Sort_way < 4))
        {
          printf("Exceed the limited range!!\n");
          exit(0);
        }

        /* Sorting */
        start_time = clock();
        switch(Sort_way)
        {
                          case 1:    //Quick
                               printf("Quick Sort\n");
                               QuickSort(Data_ary, 0, Data_num-1);
                               break;
                          case 2:    //Merge
                               printf("Merge Sort\n");
                               MALLOC(temp,Data_num * sizeof(int));
                               mergesort_new(Data_ary , temp , 0 , Data_num-1);
                               free(temp);
                               break;
                          case 3:    //Heap
                               printf("Heap Sort\n");
                               Heap_Sort(Data_ary,Data_num);
                               break;

        }
        end_time = clock();

        printAry(Data_ary , 0, Data_num);
        printf("Total sorting time : %f sec\n", (float) (end_time - start_time)/CLOCKS_PER_SEC);

        /* Free memory to reuse */
        free(Data_ary);
    }

    printf("Thanks for using! \n");
    system("PAUSE");
    return 0;
}

/* Heap Sort */
void Heap_Construct(int list[],int n)
{
    int i;
    for(i=n/2-1; i>=0; i--)
        Heap_Adjust(list, n, i);
}

void Heap_Adjust(int list[],int n,int i)
{
    int temp,large;
    temp = list[i];
    while(2*i+1 < n)
    {
        large = 2*i+1;
        if((large+1)<n && list[large]<list[large+1])
            large++;
        if(temp >= list[large])
            break;
        list[i] = list[large];
        i=large;
    }
    list[i] = temp;
}

void Heap_Sort(int list[],int n)
{
    int temp;
    Heap_Construct(list, n);
    while (n>1)
    {
        temp = list[0];
        list[0] = list[n-1];
        list[n-1] = temp;
        n--;
        Heap_Adjust(list, n, 0);
    }
}

/* Quick Sort */
void QuickSort(int a[],int left,int right)
{
    int pivot,i,j,temp=0;
    if(left < right)
    {
        i = left ; j = right + 1;
        pivot = a[left];
        //printf("init pivot = %d i=%d j=%d\n",pivot,i,j);
        do
        {
            do i++; while(a[i] < pivot && i<right);
            do j--; while(a[j] > pivot && j>left);
            //printf("[i=%d , j=%d]\n",i,j);
            if (i<j) SWAP(a[i],a[j],temp);
            //printAry(a, left,right+1);
        } while (i<j);
        SWAP(a[left],a[j],temp);
        //printAry(a, left, right+1);
        QuickSort(a, left, j-1);
        QuickSort(a, j+1, right);
    }
}

/* Merge Sort */
void mergesort_new(int list[], int temp[],int left, int right)
{
    int middle,i,j,k,n;

    if(left < right)
    {
        middle = (left+right)/2;
        mergesort_new(list, temp, left, middle);
        mergesort_new(list, temp, middle+1, right);

        i=left;
        j=middle+1;
        k=left;
        n=right-left+1;

        while(i <= middle && j <= right)
            if(list[i] <= list[j])  temp[k++] = list[i++];
            else                    temp[k++] = list[j++];

        while(i <= middle)
            temp[k++] = list[i++];
        while(j <= right)
            temp[k++] = list[j++];
        for(i=0; i<n; i++,right--)
            list[right] = temp[right];
        //printAry(list, 0, 8);
    }
}
/*
int listMerge(int a[], int link[], int start1, int start2)
{
    int last1,last2,lastResult = 0;
    for(last1 = start1 , last2 = start2; last1 && last2; )
        if(a[last1] <= a[last2])
        {
            link[lastResult] = last1;
            lastResult = last1; last1 = link[last1];
        }
        else
        {
            link[lastResult] = last2;
            lastResult = last2; last2 = link[last2];
        }

    if(last1 == 0) link[lastResult] = last2;
    else    link[lastResult] = last1;
    return link[0];
}

int reMergeSort(int a[],int link[], int left, int right)
{
    if(left >= right)   return left;
    int mid = (left+right)/2;
    return listMerge(a, link, reMergeSort(a, link, left, mid), reMergeSort(a, link, mid+1, right));
}

void Merge(int initlist[], int mergedlist[], int head, int middle, int tail)
{
    int j,k,l,t;
    j = middle + 1;
    k = head;   l = head;
    // Put element into mergedlist
    while( k<=middle && j<=tail)
    {
        if( initlist[k] < initlist[j] )
            mergedlist[l++] = initlist[k++];
        else
            mergedlist[l++] = initlist[j++];
    }

    if(k>middle)
        for(t=j; t<=tail; t++)
            mergedlist[t] = initlist[t];
    else
        for(t=k; t<=middle; t++)
            mergedlist[t] = initlist[t];
}

void MergePass(int initlist[], int mergedlist[], int n, int size)
{
    int i,j;
    for( i=1; i<=n-2*size+1; i+=2*size )
        Merge(initlist, mergedlist, i, i+size-1, i+2*size-1);
    if( (i+size-1) < n )
        Merge(initlist, mergedlist, i, i+size-1, n);
    else
        for(j=i; j<=n; j++)
            mergedlist[j] = initlist[j];
}

void MergeSort(int a[],int n)
{
    int size=1;
    int extra[MAX_SIZE];
    while(size < n)
    {
        MergePass(a, extra, n, size);
        size*=2;
        MergePass(extra, a, n, size);
        size*=2;
    }
}
*/
/* Others */
void Intro(void)
{
    printf("Welcome to use the Sorting System\n");
    printf("There are three different ways to sort your data\n");
    printf("1.Quick Sort\n");
    printf("2.Merge Sort\n");
    printf("3.Heap  Sort\n");
    printf("And you can input your own data\n");
    printf("Or we can generate if randomly\n");
    printf("So.... Let's start!\n\n");
}

void printAry(int a[],int left,int length)
{
    int i = left;
    printf("This is your data\n");
    for (; i<length ; i++)
        printf("%5d ",a[i]);
    puts("\n");
}