# 排序演算法報告
# 班級:電機一甲 姓名:陳韋誌 學號:11228135
## 泡泡排序（Bubble Sort）
#### 從第一筆資料開始，逐一比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。

#include <stdio.h>

void bubbleSort(int arr[], int n) 
{
    int i, j;
    for (i = 0; i < n-1; i++) 
    {
        for (j = 0; j < n-i-1; j++) 
        {
            if (arr[j] > arr[j+1]) 
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

#### 用10, 20, 30, 40, 50, 40, 20, 50下去排列
#### 將會輸出Sorted array: 10 20 20 30 40 40 50 50。

#include <stdio.h>

void bubbleSort(int arr[], int n) 
{
    int i, j;
    for (i = 0; i < n-1; i++) 
    {
        for (j = 0; j < n-i-1; j++) 
        {
            if (arr[j] > arr[j+1]) 
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() 
{
    int arr[] = {10, 20, 30, 40, 50, 40, 20, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


## 插入排序（Insertion Sort）
#### 將資料列假設分成已排序和未排序的兩部分，每次從未排序的資料中，挑選出一個元素，插入到已排序的資料中，直到所有的資料都已排序完成。

void insertionSort(int arr[], int n) 
{
    int i, key, j;
    for (i = 1; i < n; i++) 
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

#### 用12, 65, 5, 48, 24, 33下去排列
#### 將會輸出Sorted array: 5 12 24 33 48 65 。

#include <stdio.h>

void insertionSort(int arr[], int n) 
{
    int i, key, j;
    for (i = 1; i < n; i++) 
    {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 65, 5, 48, 24, 33};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


## 選擇排序（Selection Sort）
#### 反覆從未排序數列中找出最小值，將它與左邊的數做交換。可以有兩種方式排序，一為由大到小排序時，將最小值放到末端;若由小到大排序時，則將最小值放到前端。

#include <stdio.h>

void selectionSort(int arr[], int n) 
{
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) 
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        {
            if (arr[j] < arr[min_idx]) 
            {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

#### 用61, 45, 34, 9, 82, 16, 34下去排列
#### 將會輸出Sorted array: 9 16 34 34 45 61 82 。

#include <stdio.h>

void selectionSort(int arr[], int n) 
{
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) 
    {
        min_idx = i;
        for (j = i+1; j < n; j++)
        {
            if (arr[j] < arr[min_idx]) 
            {
                min_idx = j;
            }
        }
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {61, 45, 34, 9, 82, 16, 34};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}


## 快速排序（Quick Sort）
#### 先從原始資料列中找一個基準值(Pivot)，接著逐一將資料與基準值比較，小於基準值的資料放在左邊，大於基準值的資料放在右邊，再將兩邊區塊分別再找出基準值，重複前面的步驟，直到排序完為止。

void quickSort(int arr[], int low, int high) 
{
    if (low < high) 
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) 
{
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) 
    {
        if (arr[j] < pivot) 
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

#### 用6, 50, 49, 65, 84, 35, 4下去排列
#### 將會輸出Sorted array: 4 6 35 49 50 65 84 。

#include <stdio.h>

int partition(int arr[], int low, int high) 
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++)
    {
        if (arr[j] < pivot) 
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high) 
    {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {6, 50, 49, 65, 84, 35, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}


## 歸併排序（Merge Sort）
#### 將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

#include <stdio.h>

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        int n1 = m - l + 1;
        int n2 = r - m;
        int L[n1], R[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0, k = l;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) 
                arr[k++] = L[i++];
            else 
                arr[k++] = R[j++];
        }

        while (i < n1) 
            arr[k++] = L[i++];

        while (j < n2) 
            arr[k++] = R[j++];
    }
}

#### 用35, 46, 18, 41, 4, 35下去排列
#### 將會輸出Sorted array: 4 18 35 35 41 46。

#include <stdio.h>

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        int n1 = m - l + 1;
        int n2 = r - m;
        int L[n1], R[n2];

        for (int i = 0; i < n1; i++)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; j++)
            R[j] = arr[m + 1 + j];

        int i = 0, j = 0, k = l;

        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

int main() {
    int arr[] = {35, 46, 18, 41, 4, 35};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}


### 由上圖可知，時間複雜度:冒泡排序（Bubble Sort）< 插入排序（Insertion Sort）< 选择排序（Selection Sort）< 归并排序（Merge Sort）< 快速排序（Quick Sort）
## 心得

### 这五种排序算法各有特点，对于理解和掌握排序算法的工作原理和实现方法都是非常有益的。以下是对每种排序算法的心得体会：

### 冒泡排序：
### 冒泡排序是最简单的排序算法之一，它的思想直观清晰，易于理解和实现。然而，冒泡排序的时间复杂度较高，对于大规模数据的排序效率较低，不适合用于大规模数据的排序任务。

### 插入排序：
### 插入排序在小规模数据或者已经接近有序的数据集上有较好的表现，它的内存占用量较低，是一种稳定的排序算法。但是，对于大规模乱序的数据集，插入排序的效率不如其他排序算法。

### 选择排序：
### 选择排序是一种简单直观的排序算法，其时间复杂度与数据集的大小无关，因此在小规模数据集上具有一定的优势。但是，选择排序的性能较差，不适合用于大规模数据的排序。

### 快速排序：
### 快速排序是一种高效的排序算法，它的分治思想使得在平均情况下具有较好的性能表现。快速排序对于大规模数据集的排序任务是非常合适的，但是在最坏情况下可能会出现性能下降。

### 归并排序：
### 归并排序是一种稳定的排序算法，其分治思想和合并操作使得它在各种情况下都具有稳定的性能表现。归并排序的时间复杂度较稳定，适用于各种规模的数据集排序任务。