Untitled

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <Windows.h>
#include <chrono>

using namespace std;

const int N = 100000;
const int MAX_VAL = 5000;

//1. Thuat toan Quick Sort.
int partition(int a[], int l, int r)
{
    int mid = l + (r - l) / 2;
    swap(a[mid], a[r]);

    int pivot = a[r];
    int i = l - 1;
    for (int j = l; j < r; j++) 
    {
        if (a[j] <= pivot) 
        {
            ++i;
            swap(a[i], a[j]);
        }
    }
    ++i;
    swap(a[i], a[r]);
    return i;
}

void quickSort(int a[], int l, int r) 
{
    if (l < r) 
    {
        int p = partition(a, l, r);
        quickSort(a, l, p - 1);
        quickSort(a, p + 1, r);
    }
}

//2. Thuat toan Merge Sort.
//3. Thuat toan Heap Sort.
//4. Thuat toan Counting Sort.
void countingSort(int arr[], int n)
{
    if (n <= 0)
        return;
    int min_val = arr[0];
    int max_val = arr[0];
    for (int i = 1; i < n; i++) 
    {
        if (arr[i] > max_val) 
            max_val = arr[i];
        if (arr[i] < min_val) 
            min_val = arr[i];
    }

    int range = max_val - min_val + 1;
    int* count = new int[range];
    for (int i = 0; i < range; i++)
        count[i] = 0;

    for (int i = 0; i < n; i++)
        count[arr[i] - min_val]++;

    int vi_tri_dien = 0;
    for (int i = 0; i < range; i++)
    {
        while (count[i] > 0)
        {
            arr[vi_tri_dien] = i + min_val;
            vi_tri_dien++;
            count[i]--;
        }
    }
    delete[] count;
}

// Tao du lieu ngau nhien hoan toan.
void taoNgauNhien(int arr[], int n, int max_val) 
{
    for (int i = 0; i < n; i++) 
        arr[i] = rand() % (max_val + 1);
}

//Tao du lieu gan nhu da sap xep.
void taoGanSapXep(int arr[], int n, int max) 
{
    for (int i = 0; i < n; i++)
        arr[i] = (i * max) / n;
    for (int i = 0; i < 100; i++) 
    {
        int idx1 = rand() % n;
        int idx2 = rand() % n;
        swap(arr[idx1], arr[idx2]);
    }
}


//Tao du lieu dao nguoc hoan toan.
void taoDaoNguoc(int arr[], int n, int max_val) 
{
    int gia_tri = max_val;
    for (int i = 0; i < n; i++) 
    {
        arr[i] = gia_tri;
        if (i % (n / max_val + 1) == 0 && gia_tri > 0)
            gia_tri--;
    }
}

//Tao du lieu nhieu phan tu trung.
void taoTrungNhieu(int arr[], int n) 
{
    for (int i = 0; i < n; i++)
        arr[i] = rand() % 10;
}

void doVaInThoiGian(int thuatToan, int data[]) 
{
    string labels[] = 
    {
        "1. Kieu du lieu ngau nhien: ",
        "2. Kieu du lieu sap xep:: ",
        "3. Kieu du lieu dao nguoc: ",
        "4. Kieu du lieu trung nhau: "
    };

    for (int k = 0; k < 4; k++) 
    {
        if (k == 0) 
            taoNgauNhien(data, N, MAX_VAL);
        else if (k == 1) 
            taoGanSapXep(data, N, MAX_VAL);
        else if (k == 2) 
            taoDaoNguoc(data, N, MAX_VAL);
        else if (k == 3) 
            taoTrungNhieu(data, N);

        auto start = chrono::high_resolution_clock::now();
        switch (thuatToan) 
        {
        case 1: quickSort(data, 0, N - 1); 
            break;
        //case 2: merge_sort_cpp(data, 0, N - 1); break;
        //case 3: heap_sort_cpp(data, N); break;
        case 4: countingSort(data, N); 
            break;
        }
        auto end = chrono::high_resolution_clock::now();

        chrono::duration<double, std::milli> duration = end - start;
        cout << labels[k] << duration.count() << " ms\n";
    }
    cout << "=======================================================\n";
}

int main() 
{
    srand(time(0));
    int* data = new int[N]; 
    int choice;

    do 
    {
        cout << "\n===== HE THONG THU NGHIEM =====\n"
            << "1. Thu nghiem thuat toan Quick Sort\n"
            << "2. Thu nghiem thuat toan Merge Sort\n"
            << "3. Thu nghiem thuat toan Heap Sort\n"
            << "4. Thu nghiem thuat toan Counting Sort\n"
            << "0. Thoat chuong trinh.\n"
            << "-----------------------------------------------------------\n"
            << "Nhap lua chon cua ban: (0-4): ";
        cin >> choice;

        switch (choice) 
        {
        case 1:
            cout << "\n  THU NGHIEM QUICK SORT TREN " << N << " PHAN TU\n";
            cout << "=======================================================\n";
            doVaInThoiGian(1, data);
            break;
        case 2:
            cout << "\n  THU NGHIEM MERGE SORT TREN " << N << " PHAN TU\n";
            cout << "=======================================================\n";
            doVaInThoiGian(2, data);
            break;
        case 3:
            cout << "\n  THU NGHIEM HEAP SORT TREN " << N << " PHAN TU\n";
            cout << "=======================================================\n";
            doVaInThoiGian(3, data);
            break;
        case 4:
            cout << "\n  THU NGHIEM COUNTING SORT TREN " << N << " PHAN TU\n";
            cout << "=======================================================\n";
            doVaInThoiGian(4, data);
            break;
        case 0:
            cout << "\nDa thoat chuong trinh.\n";
            break;
        default:
            cout << "\nLua chon khong hop le. Vui long chi chon tu 0 - 4.\n";
            break;
        }
    } while (choice != 0);

    delete[] data;
    return 0;
}