CoutingSort-RadixSort-BucketSort

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

/*
Để cài đặt heap sort chúng ta cần xây dựng Maxheap or MinHeap trước
Nút lá là nút không có nút con
Nta quy ước:
- Nút trái có dạng 2i+1
- Nút phải có dạng 2i+2
- Nút cha (nút root) (i - 1)/2
- Nút lá sẽ có chỉ số từ (n/2 đến n - 1)
- Như vậy nút có nút con sé có chỉ số từ 0-> n/2 - 1
- Với n là kích thước của mảng

** Chứng minh nút lá có chỉ số từ n/2 đến n-1 như sau:
Nút lá là nút nút không có nút con nào suy ra nút đó sẽ không có nút trái và nút phải
nghĩa là:
2i + 1 >= n and 2i + 2 >= n
tương đương
i >= (n - 1)/2 and i >= (n - 2)/2
rõ ràng nếu i >= (n-1)/2 sẽ thoả mãn đc (n - 2)/2 nên ta xét:
i >= (n-1)/2 làm tròn số nguyên xuống nên lấy n/2 là thoả mãn nút lá sẽ bắt đầu từ đây

Độ phức tạp thuật toán O(NlogN)
Space complexity: O(1)


Heapify hàm này có tác dụng xây dựng lại cây MaxHeap or MinHeap

Maxheap:
*/

void PrintArr(const std::vector<int>& arr, bool isBreakLine = true)
{
    for (const auto& i : arr)
    {
        std::cout << i << " ";
    }

    if (isBreakLine)
        std::cout << "\n";
}

void Swap(int* num1, int* num2)
{
    int tmp = *num1;
    *num1 = *num2;
    *num2 = tmp;
}

void Heapify(std::vector<int>& arr, int arrSize, int idxParentNode)
{
    int left = 2 * idxParentNode + 1;
    int right = 2 * idxParentNode + 2;
    int len = arrSize;

    int newIdxParentNode = idxParentNode;

    if (left < len && arr[idxParentNode] < arr[left])
    {
        newIdxParentNode = left;
    }

    if (right < len && arr[newIdxParentNode] < arr[right])
    {
        newIdxParentNode = right;
    }

    if (newIdxParentNode != idxParentNode)
    {
        Swap(&arr[idxParentNode], &arr[newIdxParentNode]);
        Heapify(arr, len, newIdxParentNode);
    }
}

void BuildMaxHeap(std::vector<int>& arr)
{
    int len = arr.size();
    int lastNodeHasChildNode = (int) len/2 - 1;

    for (int i = lastNodeHasChildNode; i >= 0; i--)
    {
        Heapify(arr, arr.size(), i);
    }
}

void HeapSort(std::vector<int>& unsorted_arr)
{
    BuildMaxHeap(unsorted_arr);

    for (int i = unsorted_arr.size() - 1; i >= 0; i--)
    {
        Swap(&unsorted_arr[i], &unsorted_arr[0]);
        Heapify(unsorted_arr, i, 0);
    }
}


/*
Counting Sort được sử dụng khi kích thước các phần từ
nằm từ min max của mảng đó coi như tính tổng các số
hạng trong mảng đầu vào với
số các số hạng = ((số lớn nhất trong dãy - số nhỏ nhất trong dãy) / khoảng cách) + 1
với khoảng cách coi là 1 đơn vị nên số các số hạng trong dãy là n = (max - min) + 1

1) Tính n là số các số hạng trong mảng để tạo mảng count tần suất xuất hiện
các phần tử trong mảng

2) Tiếp theo tạo 1 mảng count số lượng xuất hiện của các phần tử trong
mảng đầu vào
3) Cộng dồn mảng count thì giá trị của phần tử mảng cộng dồn thể hiện
có bao nhiêu phần tử <= phần tử đang xét

Time Complexity: O(n + k)
Space Complexity: O(n + k)
*/

std::vector<int> CountingSort(const std::vector<int>& unsorted_arr)
{
    int max = unsorted_arr[0], min = unsorted_arr[0];
    for (int i = 1; i < unsorted_arr.size(); i++)
    {
        if (unsorted_arr[i] > max)
            max = unsorted_arr[i];

        if (unsorted_arr[i] < min)
            min = unsorted_arr[i];

    }

    int n = max - min + 1;
    std::vector<int> counts(n + 1, 0);

    for (const auto& e : unsorted_arr)
    {
        counts[e]++;
    }

    for (int j = 1; j <= n; j++)
    {
        counts[j] = counts[j] + counts[j - 1];
    }

    std::vector<int> ret(unsorted_arr.size());

    for (const auto& e : unsorted_arr)
    {
        int numLessOrEqualThanE = counts[e];
        if (numLessOrEqualThanE > 0)
        {
            ret[numLessOrEqualThanE - 1] = e;
            counts[e]--;
        }
    }

    return ret;
}

/*
RadixSort:
Ý tưởng: Tìm số lớn nhất để xem độ dài số là bao nhiêu
để sắp xếp theo các hàng của các số trong mảng
*/

std::vector<int> RadixSort(const std::vector<int>& unsorted_arr)
{
    int max = unsorted_arr[0];
    int len = unsorted_arr.size();

    for (int i = 1; i < unsorted_arr.size(); i++)
    {
        if (max < unsorted_arr[i])
            max = unsorted_arr[i];
    }

    int countUnit = 0;
    while (true)
    {
        int digit = max / (int) pow(10, countUnit);
        if (digit > 0)
        {
            countUnit++;
        }
        else
        {
            break;
        }
    }

    std::vector<std::vector<int>> buckets(10);
    std::vector<int> sortedArr(unsorted_arr.cbegin(), unsorted_arr.cend());

    for (int i = 0; i < countUnit; i++)
    {
        for (int j = 0; j < len; j++)
        {
            int idxBucket = (sortedArr[j] / (int) pow(10, i)) % 10;

            buckets[idxBucket].emplace_back(sortedArr[j]);
        }

        sortedArr.clear();

        for (int k = 0; k < 10; k++)
        {
            if (buckets[k].size() == 0)
                continue;

            for (const auto& e : buckets[k])
            {
                sortedArr.emplace_back(e);
            }
        }

        buckets.clear();
        buckets.resize(10);
    }

    return sortedArr;
}

void CountingSortSub(std::vector<int>& unsorted_arr, int exp)
{
    std::vector<int> counts(10, 0);
    std::vector<int> output(unsorted_arr.size());

    std::cout << "Before and exp: " << exp << std::endl;
    PrintArr(unsorted_arr);

    for (const auto& e : unsorted_arr)
    {
        int digit = (e / exp) % 10;
        std::cout << "e: " << e << " digit: " << digit << std::endl;
        counts[digit]++;
    }

    for (int i = 1; i < 10; i++)
    {
        counts[i] = counts[i] + counts[i - 1];
    }

    for (int j = unsorted_arr.size() - 1; j >= 0; j--)
    {
        int digit = (unsorted_arr[j] / exp) % 10;
        output[counts[digit] - 1] = unsorted_arr[j];
        counts[digit]--;
    }

    for(int k = 0; k < output.size(); k++)
    {
        unsorted_arr[k] = output[k];
    }

    std::cout << "[CountingSortSub]\n";
    PrintArr(unsorted_arr);
}

void RadixSort2(std::vector<int>& unsorted_arr)
{
    int max = unsorted_arr[0];
    int len = unsorted_arr.size();

    for (int i = 1; i < len; i++)
    {
        if (max < unsorted_arr[i])
            max = unsorted_arr[i];
    }

    for (int exp = 1; (max/exp) > 0; exp = 10 * exp)
    {
        CountingSortSub(unsorted_arr, exp);
    }
}

/*
Bucketsort: dùng trong trường hợp dãy là phân phối đều trên 1 khoảng
Ý tưởng:
Chia dãy vào các bucket khác nhau và sắp xếp trên từng bucket
sau đó gộp chúng vào thành mảng kết quả
*/

std::vector<int> BucketSort(const std::vector<int>& unsorted_arr)
{
    int len = unsorted_arr.size();
    int max = unsorted_arr[0];

    for (const auto& e : unsorted_arr)
    {
        if (max < e)
            max = e;
    }

    max = ceil(max / 10.0) * 10;
    int bucketSize = max / 10;
    std::vector<std::vector<int>> buckets(bucketSize);

    for (int i = 0; i < len; i++)
    {
        int idxBucket = (unsorted_arr[i] * bucketSize) / max;
        buckets[idxBucket].emplace_back(unsorted_arr[i]);
    }

    for (int i = 0; i < bucketSize; i++)
    {
        std::sort(buckets[i].begin(), buckets[i].end());
    }

    std::vector<int> ret;

    for (int i = 0; i < bucketSize; i++)
    {
        for (const auto& e : buckets[i])
        {
            ret.emplace_back(e);
        }
    }

    return ret;
}


int main()
{
    std::vector<int> arr = {4, 10, 3, 5, 1};
    // BuildMaxHeap(arr);
    HeapSort(arr);
    PrintArr(arr);

    // std::vector<int> unsorted_arr_ctSort = {4, 2, 2, 8, 3, 3, 1};
    // auto sorted_arr = CountingSort(unsorted_arr_ctSort);
    // PrintArr(sorted_arr);


    std::vector<int> unsorted_arr_radixsort = {170, 45, 75, 90, 802, 24, 2, 66};
    // RadixSort2(unsorted_arr_radixsort);
    // PrintArr(unsorted_arr_radixsort);

    auto ret = BucketSort(unsorted_arr_radixsort);
    PrintArr(ret);

    return 0;
}