# 作業 1 排序演算法簡明運動
## 函式說明
#### 將值存入到陣列中

void scanArray(int array[], int arraysize)
{
    for (int size = 0; size < arraysize; size++)
    {
        scanf("\n%d", &array[size]);
    }
} //存入array

#### 輸出陣列的值

void printArray(int array[], int arraysize)
{
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    } //印出array
}

#### 輸出陣列記憶體空間

printf("\nSize of Array: %d Bytes", sizeof(array) * arraysize / 1000); //陣列大小

#### 計算執行程式耗時

int main()
{
    int arraysize;
    int array[1000] = {0};
    double start, end;
    while (scanf("%d", &arraysize) != EOF && arraysize != 0)
    {
        start = clock(); //開始計時
        scanArray(array, arraysize);
        //執行不同排序演算法函式
        printArray(array, arraysize);
        end = clock();                                    //結束計時
        double costTime = (end - start) / CLOCKS_PER_SEC; //計算花費多少時間
        printf("\n=================================\nConsume Time: %lfms", costTime);
    return 0;
}

---

## 不同排序演算法說明

### Bubble Sort (泡泡排序)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void scanArray(int array[], int arraysize);
void bubbleSort(int array[], int arraysize);
void swap(int array[], int a, int b);
void printArray(int array[], int arraysize);

int main()
{
  int arraysize;
  int array[1000] = {0};
  double start, end;
  while (scanf("%d", &arraysize) != EOF && arraysize != 0)
  {
    start = clock(); //開始計時
    scanArray(array, arraysize);
    bubbleSort(array, arraysize);
    printArray(array, arraysize);
    end = clock(); //結束計時
    double costTime = (end - start) / CLOCKS_PER_SEC; //計算花費多少時間
    printf("\n=================================\nConsume Time: %lfms", costTime);
    printf("\nSize of Array: %d Bytes", sizeof(array) * arraysize / 1000);//陣列大小
  }
  return 0;
}

void scanArray(int array[], int arraysize)
{
  for (int size = 0; size < arraysize; size++)
  {
    scanf("\n%d", &array[size]);
  }
} //存入array

void bubbleSort(int array[], int arraysize)
{
  for (int pass = 1; pass < arraysize; pass++) //對比資料的次數減一次
  {
    int moveTime = arraysize - pass;
    for (int memory = 0; memory < moveTime; memory++)
    {
      if (array[memory] > array[memory + 1])
      {
        swap(array, memory, memory + 1);
      } //前數比後數大就交換
    }
  }
}

void swap(int array[], int a, int b) //交換函式
{
  int tmp = array[a];
  array[a] = array[b];
  array[b] = tmp;
}

void printArray(int array[], int arraysize)
{
  for (int i = 0; i < arraysize; i++)
  {
    printf("%d ", array[i]);
  } //印出array
}

---
逐步將最大的數排往最後面，對比次數為(資料數-1次)

以下為執行結果

- 時間複雜度：O(n²)
- 空間複雜度:O(1)
- Leetcode結果：TLE

---
### Insertion sort (插入排序)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void scanArray(int array[], int arraysize);
void insertionSort(int array[], int arraysize);
void printArray(int array[], int arraysize);

int main()
{
    int arraysize;
    int array[1000] = {0};
    double start, end;
    while (scanf("%d", &arraysize) != EOF && arraysize != 0)
    {
        start = clock(); //開始計時
        scanArray(array, arraysize);
        insertionSort(array, arraysize);
        printArray(array, arraysize);
        end = clock();                                    //結束計時
        double costTime = (end - start) / CLOCKS_PER_SEC; //計算花費多少時間
        printf("\n=================================\nConsume Time: %lfms", costTime);
        printf("\nSize of Array: %d Bytes", sizeof(array) * arraysize / 1000); //陣列大小
    }
    return 0;
}

void scanArray(int array[], int arraysize)
{
    for (int size = 0; size < arraysize; size++)
    {
        scanf("\n%d", &array[size]);
    }
} //存入array

void insertionSort(int array[], int arraysize)
{
    int key, comparison;
    for (int index = 1; index < arraysize; index++)
    {
        key = array[index];
        comparison = index - 1;

        while (comparison >= 0 && array[comparison] > key)
        {
            array[comparison + 1] = array[comparison];
            comparison = comparison - 1;
        }
        array[comparison + 1] = key;
    }
}

void printArray(int array[], int arraysize)
{
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    } //印出array
}

---
原理是逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。

以下為執行結果

- 時間複雜度：O(n²)
- 空間複雜度:O(1)
- Leetcode結果：TLE
- 

---
### Merge sort (合併排序)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void scanArray(int array[], int arraysize);
void merge(int array[], int low, int mid, int high);
void mergeSort(int array[], int low, int high);
void printArray(int array[], int arraysize);

int main()
{
    int arraysize;
    int array[1000] = {0};
    double start, end;
    while (scanf("%d", &arraysize) != EOF && arraysize != 0)
    {
        start = clock(); //開始計時
        scanArray(array, arraysize);
        mergeSort(array, 0, arraysize - 1);
        printArray(array, arraysize);
        end = clock();                                    //結束計時
        double costTime = (end - start) / CLOCKS_PER_SEC; //計算花費多少時間
        printf("\n=================================\nConsume Time: %lfms", costTime);
        printf("\nSize of Array: %d Bytes", sizeof(array) * arraysize / 1000); //陣列大小
    }
    return 0;
}

void scanArray(int array[], int arraysize)
{
    for (int size = 0; size < arraysize; size++)
    {
        scanf("\n%d", &array[size]);
    }
} //存入array

void merge(int array[], int low, int mid, int high)
{
    int box1, box2, stand;
    int frontmix = mid - low + 1; //前面小組的組合
    int rearmix = high - mid;     //後面小組的組合
    int left[frontmix], right[rearmix];

    for (box1 = 0; box1 < frontmix; box1++)
        left[box1] = array[low + box1]; //將前面小組存入left陣列中
    for (box2 = 0; box2 < rearmix; box2++)
        right[box2] = array[mid + 1 + box2]; //將後面小組存入right陣列中

    box1 = 0;
    box2 = 0;
    stand = low;
    while (box1 < frontmix && box2 < rearmix)
    {
        if (left[box1] <= right[box2]) //當left陣列的值比right陣列小的時候，把array陣列填入left陣列的值
        {
            array[stand] = left[box1];
            box1++; //計數器前移
        }
        else
        {
            array[stand] = right[box2];
            box2++; //計數器前移
        }
        stand++; //陣列計數器前移
    }

    while (box1 < frontmix)
    {
        array[stand] = left[box1];
        box1++;
        stand++;
    }

    while (box2 < rearmix)
    {
        array[stand] = right[box2];
        box2++;
        stand++;
    }
}

void mergeSort(int array[], int low, int high)
{
    if (low < high)
    {

        int mid = low + (high - low) / 2; //分成一半
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high); //分成一組一個資料
        merge(array, low, mid, high);    //從最小開始組合
    }
}

void printArray(int array[], int arraysize)
{
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    } //印出array
}

---
原理是會先將原始資料分割成兩個資料列，直到無法再分割，再兩兩合併各組資料，合併時也會進行該組排序，每次排序都是比較最左邊的資料，將較小的資料加到新的資料列中。

以下為執行結果

---
### Quick sort (快速排序)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void scanArray(int array[], int arraysize);
void swap(int *a, int *b);
void quickSort(int array[], int low, int high);
void printArray(int array[], int arraysize);

int main()
{
    int arraysize;
    int array[1000] = {0};
    double start, end;
    while (scanf("%d", &arraysize) != EOF && arraysize != 0)
    {
        start = clock(); //開始計時
        scanArray(array, arraysize);
        quickSort(array, 0, arraysize - 1);
        printArray(array, arraysize);
        end = clock();                                    //結束計時
        double costTime = (end - start) / CLOCKS_PER_SEC; //計算花費多少時間
        printf("\n=================================\nConsume Time: %lfms", costTime);
        printf("\nSize of Array: %d Bytes", sizeof(array) * arraysize / 1000); //陣列大小
    }
    return 0;
}

void scanArray(int array[], int arraysize)
{
    for (int size = 0; size < arraysize; size++)
    {
        scanf("\n%d", &array[size]);
    }
} //存入array

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int array[], int low, int high)
{
    int pivot = array[high]; //指標
    int i = (low - 1);       //最左邊的前一個

    for (int j = low; j <= high - 1; j++)
    {
        if (array[j] < pivot) //如果前數比指標小，從最左側存入
        {
            i++;
            swap(&array[i], &array[j]);//交換
        }
    }
    swap(&array[i + 1], &array[high]); //將指標存入比它小和比它大的數之間
    return (i + 1);                    //回傳指標位址
}

void quickSort(int array[], int low, int high)
{
    if (low < high) //直到排完
    {
        int pi = partition(array, low, high);

        quickSort(array, low, pi - 1);  //排序比指標小的
        quickSort(array, pi + 1, high); //排序比指標大的
    }
}

void printArray(int array[], int arraysize)
{
    for (int i = 0; i < arraysize; i++)
    {
        printf("%d ", array[i]);
    } //印出array
}

---
在數列中任意挑選一個數，稱為pivot，然後調整數列，使得「所有在pivot左邊的數，都比它還小，反之則比它還大。

以下為執行結果

- 時間複雜度：Ｏ(n*log n) ~ Ｏ(2)
- 時間複雜度:Ｏ(log n)
- Leetcode結果：TLE

---
### 不同排序法的記憶體用量