# 計概排序演算法報告
==11228210 黃科傑==

# 氣泡排序法

## ==THEORY==
氣泡排序（Bubble Sort）是一種簡單的排序算法，它會多次遍歷要排序的數列，每次遍歷時，相鄰的兩個元素進行比較，如果它們的順序錯誤就交換它們，直到沒有任何相鄰元素需要交換為止。這樣，最大（或最小）的元素就像氣泡一樣逐漸浮到了數列的頂端（或底端）。因此得名。

## ==EXAMPLE==

#include <stdio.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

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]) {
                swap(&arr[j], &arr[j+1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

## ==TIMER==
1. ==0.144s==
2. ==0.165s==
3. ==0.141s==

## ==COMPARISON==

對於小型數據集，氣泡排序的執行時間通常很短。但隨著數據量的增加，特別是在處理大型數據時，氣泡排序的效率會顯著下降。

# 插入排序

## ==THEORY==
插入排序（Insertion Sort）是一種簡單直觀的排序演算法，其原理是將未排序的元素逐個插入到已排序序列中的合適位置。插入排序從第二個元素開始，將該元素與已排序的子序列進行比較並插入到正確的位置，直到所有元素都被排序完成。

## ==EXAMPLE==

#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[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

## ==TIMER==
1. ==0.065s==
2. ==0.052s==
3. ==0.082s==

## ==COMPARISON==
對於小型數據集，插入排序執行時間通常很短。但隨著數據量增加，執行時間會線性增長，尤其在大型數據集上表現較差。

# 合併排序

## ==THEORY==
合併排序（Merge Sort）是一種分治算法，其核心思想是將一個數組分成兩個子數組，對每個子數組進行遞歸排序，然後將兩個已排序的子數組合併為一個有序數組。合併排序的時間複雜度為O(n log n)，其中n是要排序的元素數量。

## ==EXAMPLE==

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

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

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

    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++;
    }
}

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);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

## ==TIMER==
1. ==0.032s==
2. ==0.030s==
3. ==0.034s==

## ==COMPARISION==
合併排序的執行時間較穩定，其時間複雜度為O(n log n)。對於任意大小的數組，合併排序的執行時間都相對較長，但相對於其他複雜度相同的排序算法，它的性能通常更好。

# 選擇排序

## ==THEORY==
選擇排序（Selection Sort）是一種簡單直觀的排序算法，其原理是每次選擇待排序數組中的最小元素，並將其放置在已排序部分的末尾。選擇排序的時間複雜度為O(n^2)，其中n是要排序的元素數量。

## ==EXAMPLE==

#include <stdio.h>

void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

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;
            }
        }
        swap(&arr[min_idx], &arr[i]);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

## ==TIMER==
1. ==0.111s==
2. ==0.102s==
3. ==0.104s==

## ==COMPARISON==
選擇排序的執行時間較慢，其時間複雜度為O(n^2)。對於小型數據集，選擇排序的執行時間可能還可以接受，但隨著數據量的增加，其執行時間會快速增長，尤其是在大型數據集上表現較差。相較於其他排序算法，如快速排序和合併排序，選擇排序的效率較低。

# 整數排序-快速排序

## ==THEORY==
快速排序是一種基於分治思想的排序算法，它通過選擇一個基準元素，將數組分割成兩個子數組，並遞歸地對子數組進行排序。它的平均時間複雜度為O(n log n)，但在最壞情況下可能達到O(n^2)。

## ==EXAMPLE==

#include <stdio.h>

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

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++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    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[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

## ==TIMER==
1. ==0.042s==
2. ==0.036s==
3. ==0.043s==

## ==COMPARISON==
快速排序的執行時間取決於輸入數據的規模和特性。通常情況下，快速排序的時間複雜度為O(n log n)，但在最壞情況下可能達到O(n^2)。對於隨機或近似隨機的數據，快速排序通常表現良好並具有較短的執行時間，但在某些情況下，可能需要考慮其他排序算法以避免最壞情況的發生。

# 心得
這次藉由撰寫排序演算法報告，讓我學習如何寫出排序N個數的程式，以及學習如何讓程式輸出運行時間，除了上課老師教的4種排序法外，還找到快速排序法，其運行時間在小數據極為出色，遠超其他排序法，讓我反思，生活中不應該只侷限一種方法，可以多查詢、嘗試新的方式，或許會有預料之外的結果。