###### tags: `演算法`
# *2022/04/13 演算法作業HW01 Full*

原始碼：
[https://1drv.ms/u/s!AvwcoqTkdjpWg4w_LgieurJN7iBpew?e=j3kafa](https://1drv.ms/u/s!AvwcoqTkdjpWg4w_LgieurJN7iBpew?e=j3kafa)

//
//  main.c
//  Algorithm_HW01
//
//  Created by 吳宥陞 on 2022/4/13.
//
//  Output遞增

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#define MAX 20000
#define location_1 "D:\\Increase_Sorted_Output.txt"
#define location_2 "D:\\Decrease_Sorted_Output.txt"
#define location_3 "D:\\Random_Output.txt"

float ExchangeSorted(int*, int);
float MergeSorted_Time(int*, int);
void Merge(int*, int, int, int);
void MergeSort(int*, int, int);
void Swap(int*, int*);
float QuickSorted_Time(int*, int, int);
void QuickSort(int*, int, int);
int Partition(int*, int, int);
float BubbleSorted(int*, int);
float SelectionSorted(int*, int);

int main()
{
    clock_t start, end;
    float Total_Execution_time;
    start = clock();//Start time
    FILE *fp_1,*fp_2,*fp_3;
    fp_1 = fopen(location_1, "w+");//Open the Empty
    fp_2 = fopen(location_2, "w+");
    fp_3 = fopen(location_3, "w+");
    srand(time(NULL));//Set the seed

    float Increase_ExchangeSorted_ExecutionTime, Increase_MergeSorted_ExectionTime, Increase_QuickSorted_ExectionTime, Increase_BubbleSorted_ExectionTime, Increase_SelectionSorted_ExectionTime;//Set the execution time of Increase list
    float Decrease_ExchangeSorted_ExecutionTime, Decrease_MergeSorted_ExectionTime, Decrease_QuickSorted_ExectionTime, Decrease_BubbleSorted_ExectionTime, Decrease_SelectionSorted_ExectionTime;//Set the execution time of Decrease list
    float Random_ExchangeSorted_ExecutionTime, Random_MergeSorted_ExectionTime, Random_QuickSorted_ExectionTime, Random_BubbleSorted_ExectionTime, Random_SelectionSorted_ExectionTime;//Set the execution time of Random list

    for (int j = 1; j <= MAX; j++) {
        /*Allocate the memory size*/
        int* matrix_1_v1 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_1_v2 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_1_v3 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_1_v4 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_1_v5 = (int*)malloc(j * sizeof(int));//Store the increase matrix

        int* matrix_2_v1 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_2_v2 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_2_v3 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_2_v4 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_2_v5 = (int*)malloc(j * sizeof(int));//Store the increase matrix

        int* matrix_3_v1 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_3_v2 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_3_v3 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_3_v4 = (int*)malloc(j * sizeof(int));//Store the increase matrix
        int* matrix_3_v5 = (int*)malloc(j * sizeof(int));//Store the increase matrix

        //Initial Matrix
        for (int i = 0; i < j; i++) {
            matrix_1_v1[i] = matrix_1_v2[i] = matrix_1_v3[i] = matrix_1_v4[i] = matrix_1_v5[i] = 0.0;
            matrix_2_v1[i] = matrix_2_v2[i] = matrix_2_v3[i] = matrix_2_v4[i] = matrix_2_v5[i] = 0.0;
            matrix_3_v1[i] = matrix_3_v2[i] = matrix_3_v3[i] = matrix_3_v4[i] = matrix_3_v5[i] = 0.0;
        }

        //Create Matrix
        for (int i = 0; i < j; i++) {
            matrix_1_v1[i] = matrix_1_v2[i] = matrix_1_v3[i] = matrix_1_v4[i] = matrix_1_v5[i] = i + 1;//Increase matrix
            matrix_2_v1[i] = matrix_2_v2[i] = matrix_2_v3[i] = matrix_2_v4[i] = matrix_2_v5[i] = j - i;//Decrease matrix
            matrix_3_v1[i] = matrix_3_v2[i] = matrix_3_v3[i] = matrix_3_v4[i] = matrix_3_v5[i] = rand();//Random matrix
        }

        printf("%d nth\n", j);
        /*Show the execution time*/
        //Increase matrix
        Increase_ExchangeSorted_ExecutionTime = ExchangeSorted(matrix_1_v1, j);
        Increase_MergeSorted_ExectionTime = MergeSorted_Time(matrix_1_v2, j);
        Increase_QuickSorted_ExectionTime = QuickSorted_Time(matrix_1_v3, 0, j - 1);
        Increase_BubbleSorted_ExectionTime = BubbleSorted(matrix_1_v4, j);
        Increase_SelectionSorted_ExectionTime = SelectionSorted(matrix_1_v5, j);

        //Decrease matrix
        Decrease_ExchangeSorted_ExecutionTime = ExchangeSorted(matrix_2_v1, j);
        Decrease_MergeSorted_ExectionTime = MergeSorted_Time(matrix_2_v2, j);
        Decrease_QuickSorted_ExectionTime = QuickSorted_Time(matrix_2_v3, 0, j - 1);
        Decrease_BubbleSorted_ExectionTime = BubbleSorted(matrix_2_v4, j);
        Decrease_SelectionSorted_ExectionTime = SelectionSorted(matrix_2_v5, j);

        //Random matrix
        Random_ExchangeSorted_ExecutionTime = ExchangeSorted(matrix_3_v1, j); 
        Random_MergeSorted_ExectionTime = MergeSorted_Time(matrix_3_v2, j);
        Random_QuickSorted_ExectionTime = QuickSorted_Time(matrix_3_v3, 0, j - 1);
        Random_BubbleSorted_ExectionTime = BubbleSorted(matrix_3_v4, j);
        Random_SelectionSorted_ExectionTime = SelectionSorted(matrix_3_v5, j);

        printf("\n===================================================================================================================\n");
        /*printf("Increase_Exchange_ExecutionTime: %f\n\n", Increase_ExchangeSorted_ExecutionTime);
        printf("Decrease_Exchange_ExecutionTime: %f\n\n", Decrease_ExchangeSorted_ExecutionTime);
        printf("Random_Exchange_ExecutionTime: %f\n\n", Random_ExchangeSorted_ExecutionTime);
        printf("===================================================================================================================\n");*/

        //Output the data into file
        if (fp_1 == NULL || fp_2 == NULL || fp_3 == NULL) {
            printf("Data open Fail");
        }
        else {
            fprintf(fp_1, "%d\t%f\t", j, Increase_ExchangeSorted_ExecutionTime);
            fprintf(fp_1, "%f\t", Increase_MergeSorted_ExectionTime);
            fprintf(fp_1, "%f\t", Increase_QuickSorted_ExectionTime);
            fprintf(fp_1, "%f\t", Increase_BubbleSorted_ExectionTime);
            fprintf(fp_1, "%f\n", Increase_SelectionSorted_ExectionTime);

            fprintf(fp_2, "%d\t%f\t", j, Decrease_ExchangeSorted_ExecutionTime);
            fprintf(fp_2, "%f\t", Decrease_MergeSorted_ExectionTime);
            fprintf(fp_2, "%f\t", Decrease_QuickSorted_ExectionTime);
            fprintf(fp_2, "%f\t",  Decrease_BubbleSorted_ExectionTime);
            fprintf(fp_2, "%f\n", Decrease_SelectionSorted_ExectionTime);

            fprintf(fp_3, "%d\t%f\t", j, Random_ExchangeSorted_ExecutionTime);
            fprintf(fp_3, "%f\t", Random_MergeSorted_ExectionTime);
            fprintf(fp_3, "%f\t", Random_QuickSorted_ExectionTime);
            fprintf(fp_3, "%f\t", Random_BubbleSorted_ExectionTime);
            fprintf(fp_3, "%f\n", Random_SelectionSorted_ExectionTime);
        }

        free(matrix_1_v1); free(matrix_1_v2); free(matrix_1_v3); free(matrix_1_v4); free(matrix_1_v5);//Free the memory of Increase Matrix
        free(matrix_2_v1); free(matrix_2_v2); free(matrix_2_v3); free(matrix_2_v4); free(matrix_2_v5);//Free the memory of Decrease Matrix
        free(matrix_3_v1); free(matrix_3_v2); free(matrix_3_v3); free(matrix_3_v4); free(matrix_3_v5);//Free the memory of random Matrix
    }
    fclose(fp_1);
    fclose(fp_2);
    fclose(fp_3);
    end = clock();//End time
    Total_Execution_time = end - start;
    printf("\n\n===================================================================================================================\n");
    printf("Total Execution Time: %.0f ms\n",Total_Execution_time);
}

//Swap Function
void Swap(int* NUM_1, int* NUM_2) {
    int Temp = *NUM_1;
    *NUM_1 = *NUM_2;
    *NUM_2 = Temp;
}

//Exchange Sort
float ExchangeSorted(int* matrix, int MatrixSize) {
    clock_t start, end;
    float execution_time;
    start = clock();//Start time

    //Main ExchangeSort Function
    for (int i = 0; i < MatrixSize - 1; i++) {//Control the Basic Number
        for (int j = i + 1; j < MatrixSize; j++) {//Control the Compare Number
            if ((matrix && matrix[i] > matrix[j])) {
                Swap(&matrix[i], &matrix[j]);
            }
        }
    }

    end = clock();//End time
    execution_time = end - start;
    return execution_time;//Return the Execution Time
}

//Merge Sort Execution Time
float MergeSorted_Time(int* Matrix, int MatrixSize) {
    clock_t start, end;
    float execution_time;
    start = clock();//Start time

    //Call the MergeSort Function
    MergeSort(Matrix, 0, MatrixSize-1);

    end = clock();//End time
    execution_time = end - start;
    return execution_time;//Return the Execution Time
}

//Merge Function
void Merge(int* matrix, int Left, int Middle, int Right) {
    int LeftIndex = Left;
    int RightIndex = Middle + 1;
    int TempMatrixLength = Right - Left + 1;
    int* TempMatrix = (int*)malloc(TempMatrixLength * sizeof(int));//Allocate a temp matrix
    int TempMatrixIndex = 0;


    while (LeftIndex <= Middle && RightIndex <= Right) {
        if (matrix[LeftIndex] <= matrix[RightIndex]) {
            TempMatrix[TempMatrixIndex] = matrix[LeftIndex];
            LeftIndex++;
        }
        else {
            TempMatrix[TempMatrixIndex] = matrix[RightIndex];
            RightIndex++;
        }
        TempMatrixIndex++;
    }

    if (LeftIndex > Middle) {
        while (RightIndex <= Right) {
            TempMatrix[TempMatrixIndex] = matrix[RightIndex];
            RightIndex++;
            TempMatrixIndex++;
        }
    }
    else {
        while (LeftIndex <= Middle) {
            TempMatrix[TempMatrixIndex] = matrix[LeftIndex];
            LeftIndex++;
            TempMatrixIndex++;
        }
    }
    LeftIndex = Left;

    for (TempMatrixIndex = 0; TempMatrixIndex < TempMatrixLength; TempMatrixIndex++) {
        matrix[LeftIndex] = TempMatrix[TempMatrixIndex];
        LeftIndex++;
    }

    free(TempMatrix);
}

//Merge Sort Function
void MergeSort(int* matrix, int Left, int Right) {
    if (Left < Right) {
        int mid = (Left + Right) / 2;
        MergeSort(matrix, Left, mid);
        MergeSort(matrix, mid + 1, Right);
        Merge(matrix, Left, mid, Right);
    }
}

//Quick Sort Execution Time 
float QuickSorted_Time(int* matrix, int Left, int Right) {
    clock_t start, end;
    float execution_time;
    start = clock();//Start time
    QuickSort(matrix, Left, Right);
    end = clock();//End time
    execution_time = end - start;
    return execution_time;
}

//Quick Sort Main Function 
void QuickSort(int* matrix, int Left, int Right) {
    //Main Quick Sort Function
    if (Left < Right) {
        int Pivot = Partition(matrix, Left, Right);//Set the Pivot of index
        QuickSort(matrix, Left, Pivot - 1);//Deal with the Left of Pivot
        QuickSort(matrix, Pivot + 1, Right);//Deal with the Right of Pivot
    }
}

//Partition
int Partition(int* matrix, int Left, int Right) {

    int Pivot = matrix[Right];//Default Set the Pivot to the Right Element
    int i = Left - 1;
    for (int j = Left; j < Right; j++) {
        if (matrix[j] < Pivot) {
            i++;
            Swap(&matrix[i], &matrix[j]);
        }
    }
    i++;
    Swap(&matrix[i], &matrix[Right]);
    return i;
}

//Bubble Sort
float BubbleSorted(int* matrix, int MatrixSize) {
    clock_t start, end;
    float execution_time;
    start = clock();//Start time

    //Main BubbleSort Function
    for (int i = 0; i < MatrixSize - 1; i++) {
        for (int j = i + 1; j < MatrixSize; j++) {
            if (matrix && matrix[i] > matrix[j]) {
                Swap(&matrix[i], &matrix[j]);
            }
        }
    }

    end = clock();//End time
    execution_time = end - start;
    return execution_time;//Return the Execution Time
}

//Selection Sort
float SelectionSorted(int* matrix, int MatrixSize) {
    clock_t start, end;
    float execution_time;
    start = clock();//Start time

    //Main SelectionSort Function
    for (int i = 0; i < MatrixSize - 1; i++) {//Control the Basic Number
        int Temp = i;//Store the min number's index
        for (int j = i + 1; j < MatrixSize; j++) {//Control the Compare Number
            if ((matrix && matrix[Temp] > matrix[j])) {
                Temp = j;
            }
        }
        if (i != Temp) {//Direction change the min number with the most left number of this round
            Swap(&matrix[i], &matrix[Temp]);
        }
    }

    end = clock();//End time
    execution_time = end - start;
    return execution_time;//Return the Execution Time
}