//
// Created by grtsinry43 on 5/8/25.
//

#include "problem3.h"

#include <vector>
#include <iostream>
#include <random>
#include <ctime>

int partition(std::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++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quick_sort(std::vector<int> &arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quick_sort(arr, low, pivot - 1);
        quick_sort(arr, pivot + 1, high);
    }
}

void select_sort(std::vector<int> &arr) {
    for (size_t i = 0; i < arr.size() - 1; i++) {
        size_t min_index = i;
        for (size_t j = i + 1; j < arr.size(); j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        std::swap(arr[i], arr[min_index]);
    }
}

void insert_sort(std::vector<int> &arr) {
    for (int i = 0; i < arr.size(); ++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;
    }
}

std::vector<int> generate_random_array(int size) {
    std::vector<int> arr(size);
    for (int i = 0; i < size; ++i) {
        arr[i] = random() % 10000; // 范围给一个0-9999吧
    }
    return arr;
}

int problem_3() {
    int size = 10000;
    std::vector<int> arr = generate_random_array(size);
    std::vector<int> arr_copy = arr;
    std::vector<int> arr_copy2 = arr;
    // 快速排序
    clock_t start, end;
    start = clock();
    quick_sort(arr, 0, arr.size() - 1);
    end = clock();
    double quick_sort_time = double(end - start) / CLOCKS_PER_SEC;
    std::cout << "Quick Sort Time: " << quick_sort_time << " seconds\n";

    // 选择排序
    start = clock();
    select_sort(arr_copy);
    end = clock();
    double select_sort_time = double(end - start) / CLOCKS_PER_SEC;
    std::cout << "Select Sort Time: " << select_sort_time << " seconds\n";

    // 插入排序
    start = clock();
    insert_sort(arr_copy2);
    end = clock();
    double insert_sort_time = double(end - start) / CLOCKS_PER_SEC;
    std::cout << "Insert Sort Time: " << insert_sort_time << " seconds\n";


    return 0;
}