#include "head.h"

//=== === === RADIX SORT === === ===
uint32_t get_max(uint32_t* arr,uint32_t n);
void counting_sort(uint32_t* arr, uint32_t n, uint32_t exp);
void sort_radix(uint32_t* arr,uint32_t n){
    uint32_t max = get_max(arr, n);

    for(uint32_t exp = 1; max / exp > 0; exp *= 10)
        counting_sort(arr, n, exp);
}
uint32_t get_max(uint32_t* arr, uint32_t n) {
    uint32_t max = arr[0];
    for(uint32_t i = 1; i < n; i++)
        if(arr[i] > max)
            max = arr[i];
    return max;
}
void counting_sort(uint32_t* arr, uint32_t n, uint32_t exp) {
    uint32_t output[n];
    uint32_t count[10] = {0};

    for(uint32_t i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for(uint32_t i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for(uint32_t i = n; i-- > 0;){
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for(uint32_t i = 0; i < n; i++)
        arr[i] = output[i];
}
// === === === HEAP SORT  === === ===
void heapify(uint32_t* arr, uint32_t n, uint32_t i);
void swap(uint32_t* a, uint32_t *b);
void sort_heap(uint32_t* arr,uint32_t n){
    for(int i = n/2 - 1; i >= 0; i--)    
     heapify(arr, n, i);

    for(uint32_t i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}
void swap(uint32_t* a, uint32_t *b) {
    uint32_t temp = *a;
    *a = *b;
    *b = temp;
}
void heapify(uint32_t* arr, uint32_t n, uint32_t i) {
    uint32_t largest = i;
    uint32_t left = 2 * i + 1;
    uint32_t right = 2 * i + 2;

    if(left < n && arr[left] > arr[largest])
        largest = left;

    if(right < n && arr[right] > arr[largest])
        largest = right;

    if(largest != i) {
        swap(&arr[i], &arr[largest]);
        
        heapify(arr, n, largest);
    }
}

// === === === BUBBLE SORT === === ===
void sort_bubble(uint32_t* arr,uint32_t n){
    for(uint32_t i = 0; i < n - 1; i++) {
        uint32_t swapped = 0;
        for(uint32_t j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                uint32_t temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if(!swapped) break; 
    }
}

// === === === MERGE SORT === === ===
void sort_merge(uint32_t* arr, uint32_t left, uint32_t right)
{
    uint32_t n = right - left + 1;

    uint32_t *temp = malloc(sizeof(uint32_t) * n);
    if(!temp) return;

    for(uint32_t size = 1; size < n; size *= 2)
    {
        for(uint32_t start = 0; start < n; start += 2 * size)
        {
            uint32_t mid = start + size;
            uint32_t end = start + 2 * size;

            if(mid > n) mid = n;
            if(end > n) end = n;

            uint32_t i = start;
            uint32_t j = mid;
            uint32_t k = start;

            while(i < mid && j < end)
            {
                if(arr[left + i] <= arr[left + j])
                    temp[k++] = arr[left + i++];
                else
                    temp[k++] = arr[left + j++];
            }

            while(i < mid)
                temp[k++] = arr[left + i++];

            while(j < end)
                temp[k++] = arr[left + j++];
        }

        for(uint32_t i = 0; i < n; i++)
            arr[left + i] = temp[i];
    }

    free(temp);
}