#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Bubble Sort mark:3-4
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Selection Sort
// 1. 先選這輪的最小
// 2. 跟i交換
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

// Insertion Sort
// 1. 依序給這一輪的value
// 2. value跟前面的比
// 3. 放到完成的位置
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {5, 2, 8, 3, 1};

    // Bubble Sort
    bubbleSort(arr);
    cout << "Bubble Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // Selection Sort
    arr = {5, 2, 8, 3, 1};
    selectionSort(arr);
    cout << "Selection Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // Insertion Sort
    arr = {5, 2, 8, 3, 1};
    insertionSort(arr);
    cout << "Insertion Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

// 快速排序 (Quick Sort)
// 最壞情況時間複雜度：O(n^2)
// 平均情況時間複雜度：O(nlogn)
// 最佳情況時間複雜度：O(nlogn)
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high]; // 選擇最後一個元素作為主元
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);

        // 遞迴地對分割後的子陣列進行排序
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}
int main() {
    vector<int> arr = {5, 2, 8, 3, 1};

    // 快速排序
    cout << "快速排序結果：" << endl;
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}