Algorithms_sort

void Make_3_Heap(int64_t* arr, int n, int i)
{
    int root = i;

    int l = 2 * i + 1;
    int m = 2 * i + 2;
    int r = 2 * i + 3;

    if (l < n && arr[l] > arr[root])
        root = l;
    if (m < n && arr[m] > arr[root])
        root = m;
    if (r < n && arr[r] > arr[root])
        root = r;

    if (root != i)
    {
        swap(arr[i], arr[root]);
        Make_3_Heap(arr, n, root);
    }
}

void Sort_3_Heap(int64_t* arr, int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        Make_3_Heap(arr, n, i);

    for (int i = n - 1; i >= 0; i--)
    {
        swap(arr[0], arr[i]);

        Make_3_Heap(arr, i, 0);
    }
}

int Divide(int *b, int il, int j)
{
    int pivot = b[j];

    int pIndex = il;


    for (int i = il; i < j; i++)
    {
        if (b[i] <= pivot)
        {
            swap(b[i], b[pIndex]);
            pIndex++;
        }
    }

    swap(b[pIndex], b[j]);

    return pIndex;
}

void QuickSort(int* b, int i, int j)
{
    if (i >= j)
    {
        return;
    }
    int pivot = Divide(b, i, j);
    QuickSort(b, i, pivot - 1); QuickSort(b, pivot + 1, j);
}

class DHeap
{
private:
    int d = 3;
    int64_t* heap_pointer;
    int64_t heap_size;
public:
    void heapify(int64_t* arr_point, int64_t arr_size)
    {
        heap_size = arr_size;
        heap_pointer = new int64_t[heap_size];
        for (int i = 0; i < heap_size; i++)
        {
            heap_pointer[i] = 0;
        }
        for (int i = 0; i < heap_size; i++)
        {
            insert(arr_point[i], i);
        }
    }
    void insert(int64_t value, int i)
    {
        heap_pointer[i] = value;
        bubble_up(i);
    }
    int bubble_up(int index)
    {
        int parent_index = (index - 1) / d;
        if (index == 0 || heap_pointer[parent_index] >= heap_pointer[index])
        {
            return index;
        }
        else
        {
            swap(heap_pointer[parent_index], heap_pointer[index]);
            return bubble_up(parent_index);
        }
    }
    void printHeap() {
        for (int i = 0; i < heap_size; ++i)
        {
            cout << heap_pointer[i] << " ";
        }
        cout << std::endl;
    }
    int getMaxElement()
    {
        return heap_pointer[0];
    }
    void Make_3_Heap(int64_t* arr, int n, int i)
    {
        int root = i;

        int l = 2 * i + 1;
        int m = 2 * i + 2;
        int r = 2 * i + 3;

        if (l < n && arr[l] > arr[root])
            root = l;
        if (m < n && arr[m] > arr[root])
            root = m;
        if (r < n && arr[r] > arr[root])
            root = r;

        if (root != i)
        {
            swap(arr[i], arr[root]);
            Make_3_Heap(arr, n, root);
        }
    }
    void sort()
    {
        for (int i = heap_size / 2 - 1; i >= 0; i--)
            Make_3_Heap(heap_pointer, heap_size, i);

        for (int i = heap_size - 1; i >= 0; i--)
        {
            swap(heap_pointer[0], heap_pointer[i]);

            Make_3_Heap(heap_pointer, i, 0);
        }
    }
};

void MakePseudoRandomSorted_3_Heap_Array(int size, ofstream& _file)
{
    srand(time(NULL));

    DHeap heap_rand_sort;

    int64_t* rand_arr;
    rand_arr = new int64_t[size];

    cout << "\n";

    cout << "Making unsorted random array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        rand_arr[i] = rand() % 1'000'000'000;
    }

    heap_rand_sort.heapify(rand_arr, size);
    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    heap_rand_sort.sort();
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void MakeSortedIncreasingArray_3_Heap(int size, ofstream& _file)
{
    DHeap heap_inc_sort;

    int64_t* arr;
    arr = new int64_t[size];

    cout << "\n";
    cout << "Making increasing array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        arr[i] = i;
    }

    heap_inc_sort.heapify(arr, size);
    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    heap_inc_sort.sort();
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void MakeSortedDecreasingArray_3_Heap(int size, ofstream& _file)
{
    DHeap heap_inc_sort;

    int64_t* arr;
    arr = new int64_t[size];

    cout << "\n";
    cout << "Making increasing array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        arr[i] = size - i;
    }

    heap_inc_sort.heapify(arr, size);
    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    heap_inc_sort.sort();
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void MakePseudoRandomSortedQuickArray(int size, ofstream& _file)
{
    srand(time(NULL));

    int64_t* arr;
    arr = new int64_t[size];

    cout << "\n";
    cout << "Making unsorted random array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        arr[i] = rand() % 1'000'000'000;
    }
    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    QuickSort(arr, 0, size - 1);
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void MakeSortedIncreasingQuickArray(int size, ofstream& _file)
{
    int64_t* arr;
    arr = new int64_t[size];

    cout << "\n";
    cout << "Making increasing array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        arr[i] = i;
    }

    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    QuickSort(arr, 0, size - 1);
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void MakeSortedDecreasingQuickArray(int size, ofstream& _file)
{
    int64_t* arr;
    arr = new int64_t[size];

    cout << "\n";
    cout << "Making decreasing array of " << size << " elements" << "\n";

    for (int i = 0; i < size; i++)
    {
        arr[i] = size - i;
    }

    cout << "Made an array" << "\n";

    auto start = high_resolution_clock::now();

    QuickSort(arr, 0, size - 1);
    cout << "Array sorted";

    auto stop = high_resolution_clock::now();

    auto duration = duration_cast<milliseconds>(stop - start);
    _file << "Time taken to sort an array of " << size << " elements: " << duration.count() << " milliseconds" << "\n";

    cout << "\n";
}

void SortTestFirstCase(ofstream& file)
{
    cout << "\n";

    //-----------------------------3-Heap Sorts-----------------------------//
    file << "First Case: " << "\n\n\n";
    file << "Time measurments for 3-heap sorting a pseudo random array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakePseudoRandomSorted_3_Heap_Array(i, file);
    }
    file << "\n\n";
    file << "Time measurments for 3-heap sorting an increasing array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakeSortedIncreasingArray_3_Heap(i, file);
    }
    file << "\n\n";
    file << "Time measurments for 3-heap sorting a decreasing array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakeSortedDecreasingArray_3_Heap(i, file);
    }

    //-------------------------Quick Sorts-------------------------//

    file << "\n\n";
    file << "Time measurments for quick sorting a pseudo random array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakePseudoRandomSortedQuickArray(i, file);
    }
    file << "\n\n";
    file << "Time measurments for quick sorting an increasing array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakeSortedIncreasingQuickArray(i, file);
    }
    file << "\n\n";
    file << "Time measurments for quick sorting a decreasing array with numbers which have a maximum value of 10^9" << "\n";
    for (int64_t i = 1; i <= 1'000'001; i += 10'000)
    {
        MakeSortedDecreasingQuickArray(i, file);
    }
}

class DHeap
{
private:
    int d = 3;
    int64_t* heap_pointer;
    int64_t heap_size;
public:
    void heapify(int64_t* arr_point, int64_t arr_size)
    {
        heap_size = arr_size;
        heap_pointer = new int64_t[heap_size];
        for (int i = 0; i < heap_size; i++)
        {
            heap_pointer[i] = 0;
        }
        for (int i = 0; i < heap_size; i++)
        {
            insert(arr_point[i], i);
        }
    }
    void insert(int64_t value, int i)
    {
        heap_pointer[i] = value;
        bubble_up(i);
    }
    int bubble_up(int index)
    {
        int parent_index = (index - 1) / d;
        if (index == 0 || heap_pointer[parent_index] >= heap_pointer[index])
        {
            return index;
        }
        else
        {
            swap(heap_pointer[parent_index], heap_pointer[index]);
            return bubble_up(parent_index);
        }
    }
    void printHeap() {
        for (int i = 0; i < heap_size; ++i)
        {
            cout << heap_pointer[i] << " ";
        }
        cout << std::endl;
    }
    int getMaxElement()
    {
        return heap_pointer[0];
    }
    void Make_3_Heap(int64_t* arr, int n, int i)
    {
        int root = i;

        int l = 2 * i + 1;
        int m = 2 * i + 2;
        int r = 2 * i + 3;

        if (l < n && arr[l] > arr[root])
            root = l;
        if (m < n && arr[m] > arr[root])
            root = m;
        if (r < n && arr[r] > arr[root])
            root = r;

        if (root != i)
        {
            swap(arr[i], arr[root]);
            Make_3_Heap(arr, n, root);
        }
    }
    void sort()
    {
        for (int i = heap_size / 2 - 1; i >= 0; i--)
            Make_3_Heap(heap_pointer, heap_size, i);

        for (int i = heap_size - 1; i >= 0; i--)
        {
            swap(heap_pointer[0], heap_pointer[i]);

            Make_3_Heap(heap_pointer, i, 0);
        }
    }
};