Sortowania

//ALGO2 IS1 211A LAB05
//Jakub Ogryzek
//oj44443@zut.edu.pl
#include "pch.h"
#include <iostream>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <memory>
#include <string>
#include <random>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;

template <typename T>
class Heap {
public:
    T *data = new T[capacity];
    int capacity;
    int size;
    Heap()
    {
        size = 0;
        capacity = 1;
        data = new T[capacity];
    }
    Heap(int tab_size, T* tab)
    {
        size = tab_size;
        capacity = tab_size;
        data = new T[capacity];
        for (int i = 0; i < tab_size; i++)
            data[i] = tab[i];
    }
    ~Heap()
    {
        delete[] data;
        data = nullptr;
        size = 0;
        capacity = 0;
    }

    int Push(int size)
    {
        if (size == 0)
            return 0;
        int parent_index = parent(size);
        if (parent_index < 0)
            return 0;
        if (data[size] <= data[parent_index])
            return 0;
        swap(data[size], data[parent_index]);
        return Push(parent_index);
    }

    void AddNewElement(const T&input)
    {
        size = size + 1;
        if (size <= capacity) {
            data[size - 1] = input;
        }
        if (size > capacity)
        {
            capacity = capacity * 2;
            T *temp = new T[capacity];
            for (int i = 0; i < size - 1; i++)
            {
                temp[i] = move(data[i]);
            }
            temp[size - 1] = input;
            delete[] data;
            data = temp;
        }
        Push(size - 1);
    }
    T DeleteRoot(int index)
    {
        if (size == 0)
        {
            throw out_of_range("ERROR");
        }
        if (size == 1)
        {
            T temp = data[0];
            return temp;
        }
        swap(data[0], data[size - 1]);
        size = size - 1;
        DeleteRootRek(0);
        T temp = data[size];
        return temp;
    }

    void DeleteRootRek(int index)
    {
        int highest_value = index;
        int left = left_son(index);
        int right = right_son(index);
        if (left < size)
            if (data[highest_value] < data[left])
                highest_value = left;
        if (right < size)
            if (data[highest_value] < data[right])
                highest_value = right;
        if (highest_value != index)
        {
            swap(data[index], data[highest_value]);
            DeleteRootRek(highest_value);
        }
    }

    int parent(int index)
    {
        return (index - 1) / 2;
    }
    int left_son(int index)
    {
        return 2 * index + 1;
    }
    int right_son(int index)
    {
        return 2 * index + 2;
    }

    void ToString()
    {
        cout << "Kopiec:" << endl;
        cout << "Liczba elementow: " << size << endl;
        int dzielenie = 1;
        for (int i = 0; i < size; i++)
        {
            cout << data[i] << ", ";
        }
        cout << endl;
    }

    void ClearHeap()
    {
        cout << "Kopiec zostal wyczyszczony" << endl;
        for (int i = 0; i < size; i++)
        {
            data[i].~T();
        }
        size = 0;
        capacity = 1;
    }

    void ChangeTabIntoHeap(int tab_size)
    {
        int par = parent(tab_size - 1);
        if (par >= 0)
        {
            DeleteRootRek(par);
            ChangeTabIntoHeap(tab_size - 1);
        }
    }
    void HeapSort(int tab_size, int flag)
    {
        T* result_tab = new T[tab_size];
        for (int i = tab_size - 1; i >= 0; i--)
        {
            result_tab[i] = DeleteRoot(0);
        }
        if (flag == 1)
        {
            if (tab_size >= 10)
            {
                for (int i = 0; i < 3; i++)
                {
                    cout << result_tab[i] << " ";
                }
                cout << "(...) ";
                for (int i = tab_size - 3; i < tab_size; i++)
                {
                    cout << result_tab[i] << " ";
                }
            }
            else
            {
                for (int i = 0; i < tab_size; i++)
                {
                    cout << result_tab[i] << " ";
                }
            }
        }
        delete[] result_tab;
    }
};

struct Struktura
{
    int pole1;
    Struktura()
    {
        pole1 = rand() % 30000 + 1;
    }
    Struktura(int a)
    {
        pole1 = a;
    }
    bool operator ==(const Struktura&n) const
    {
        return pole1 == n.pole1;
    }
    bool operator >(const Struktura&n) const
    {
        return pole1 > n.pole1;
    }
    bool operator <(const Struktura&n) const
    {
        return pole1 < n.pole1;
    }
    bool operator <=(const Struktura&n) const
    {
        return pole1 <= n.pole1;
    }
    bool operator >=(const Struktura&n) const
    {
        return pole1 >= n.pole1;
    }
    bool operator /(const Struktura&n) const
    {
        return pole1 / n.pole1;
    }
    //bool operator =(const Struktura&n)
    //{
        //return pole1 = n.pole1;
    //}
};

ostream& operator <<(ostream&stream, const Struktura&m)
{
    return (stream << m.pole1);
}

template <typename T>
T FindRange(T *tab, int tab_size)
{
    T max;
    max = tab[0];
    for (int i = 1; i < tab_size; i++)
    {
        if (tab[i] > max)
            max = tab[i];
    }
    return max;
}

template <typename T>
void CountingSort(T *tab, int tab_size)
{
    int range = FindRange(tab, tab_size);
    T* result_tab = new T[tab_size];
    T* count = new T[range + 1];
    //Wyzerowanie tablicy zliczającej
    for (int i = 0; i <= range; i++)
    {
        count[i] = 0;
    }
    //Zliczanie
    for (int i = 0; i < tab_size; i++)
    {
        count[tab[i]] += 1;
    }
    cout << endl;
    //Sprawdzenie
    /*cout << "Zliczanie:" << endl;
    for (int i = 0; i <= range; i++)
    {
        cout << i << "\t" << count[i] << endl;
    }*/
    //Wyznaczenie tablicy wynikowej
    int counter;
    int sum = 0;
    for (int i = 0; i <= range; i++)
    {
        counter = count[i];
        for (int j = 1; j <= counter; j++)
        {
            result_tab[sum] = i;
            sum += 1;
        }
    }
    //Sprawdzenie2
    /*cout << "Posortowane:" << endl;
    for (int i = 0; i < tab_size; i++)
    {
        cout << i << "\t" << result_tab[i] << endl;
    }*/
    //Nadpisanie tablicy wejściowej
    for (int i = 0; i < tab_size; i++)
    {
        tab[i] = result_tab[i];
    }
    delete[] result_tab;
    delete[] count;
}

void Bucket_Sort_Int(int *tab, int rozmiar, int m)
{
    //Tworzenie wiader
    vector<vector<int>> bucket(m);
    int max = tab[0];
    for (int i = 0; i < rozmiar; i++)
    {
        if (tab[i] > max)
            max = tab[i];
    }
    //max = max + 1;
    //Wsadzanie elementow do wiader
    for (int i = 0; i < rozmiar; i++)
    {
        bucket[floor((tab[i]) / (double(max)*rozmiar))].push_back(tab[i]);
    }
    //Sortowanie
    for (int i = 0; i < m; i++)
    {
        sort(bucket[i].begin(), bucket[i].end());
    }
    //Wklejanie wiader do wejściowej tablicy
    int index = 0;
    for (int i = 0; i < rozmiar; i++)
    {
        for (int j = 0; j < bucket[i].size(); j++)
        {
            tab[index] = bucket[i][j];
            index = index + 1;
        }
    }
    //Sprawdzenie2
    /*cout << "Posortowane:" << endl;
    for (int i = 0; i < rozmiar; i++)
    {
        cout << i << "\t" << tab[i] << endl;
    }*/
}

template <typename T>
void Bucket_Sort_Templates(T *tab, int rozmiar, int m)
{
    //Tworzenie wiader
    vector<vector<T>> bucket(m);
    int max = tab[0].pole1;
    for (int i = 0; i < rozmiar; i++)
    {
        if (tab[i] > max)
            max = tab[i].pole1;
    }
    //max = max + 1;
    //Wsadzanie elementow do wiader
    for (int i = 0; i < rozmiar; i++)
    {
        //bucket[floor((tab[i].pole1) / (double(max)*rozmiar))].push_back(tab[i]);
        bucket[floor((tab[i].pole1 / (double(max)*rozmiar)))].push_back(tab[i]);
    }
    //Sortowanie
    for (int i = 0; i < m; i++)
    {
        sort(bucket[i].begin(), bucket[i].end());
    }
    //Wklejanie wiader do wejściowej tablicy
    int index = 0;
    for (int i = 0; i < rozmiar; i++)
    {
        for (int j = 0; j < bucket[i].size(); j++)
        {
            tab[index] = bucket[i][j];
            index = index + 1;
        }
    }
    //Sprawdzenie2
    /*cout << "Posortowane:" << endl;
    for (int i = 0; i < rozmiar; i++)
    {
        cout << i << "\t" << tab[i] << endl;
    }*/
}

void ShortenedTabInt(int *tab, int tab_size)
{
    if (tab_size >= 10)
    {
        for (int i = 0; i < 3; i++)
        {
            cout << tab[i] << " ";
        }
        cout << "(...) ";
        for (int i = tab_size-3; i < tab_size; i++)
        {
            cout << tab[i] << " ";
        }
    }
    else
    {
        for (int i = 0; i < tab_size; i++)
        {
            cout << tab[i] << " ";
        }
    }
}

int main()
{
    //int tab1[30] = { 40,25,16,34,27,12,11,5,50,7,1,9,8,6,13,15,37,32,13,11,4,13,2,47,26,39,42,12,11,30 };
    //cout << "Heap sort:" << endl;
    //Heap<int> *heap = new Heap<int>(30, tab1);
    //heap->ChangeTabIntoHeap(30);
    //heap->HeapSort(30, 1);

    /*int tab1[10] = { 40,25,16,34,27,12,11,5,50,7 };
    cout << "Tablica przed posortowaniem:" << endl;
    for (int i = 0; i < 10; i++)
        cout << tab1[i] << " ";
    cout << "\n";
    ShortenedTabInt(tab1, 10);
    int tab2[10];
    memcpy(tab2, tab1, 10 * sizeof(int));
    int tab3[10];
    memcpy(tab3, tab1, 10 * sizeof(int));
    cout << "\nCounting sort:";
    CountingSort(tab1, 10);
    for (int i = 0; i < 10; i++)
        cout << tab1[i] << " ";
    cout << "\n";
    ShortenedTabInt(tab1, 10);
    cout << "\nBucket sort:" << endl;
    Bucket_Sort_Int(tab2, 10, 50);
    for (int i = 0; i < 10; i++)
        cout << tab2[i] << " ";
    cout << "\n";
    ShortenedTabInt(tab2, 10);
    cout << "\nHeap sort:" << endl;
    Heap<int> *heap = new Heap<int>(10, tab3);
    heap->ChangeTabIntoHeap(10);
    heap->HeapSort(10, 1);*/

    cout << "LICZBY CALKOWITE:" << endl;
    srand(0);
    const int MAX_ORDER = 7;
    const int m = pow(10, 7);
    for (int o = 1; o <= MAX_ORDER; o++)
    {
        const int n = pow(10, o);
        cout << n << " Elementow w tablicy:";
        int* array1 = new int[n];
        for (int i = 0; i < n; i++)
        {
            int rand_val = (rand() % 10000000) + 1;
            array1[i] = rand_val;
        }
        cout << "\nPoczatkowa tablica:\n";
        ShortenedTabInt(array1, n);
        int *array2 = new int[n];
        int *array3 = new int[n];
        memcpy(array2, array1, n * sizeof(int));
        memcpy(array3, array1, n * sizeof(int));
        //CountingSort
        clock_t t1 = clock();
        CountingSort(array1, n);
        ShortenedTabInt(array1, n);
        clock_t t2 = clock();
        cout << "Czas wykonania CountingSort to: " << (double)(t2 - t1) / CLOCKS_PER_SEC << " sekundy" << endl;
        //HeapSort
        clock_t t3 = clock();
        Heap<int> *heap = new Heap<int>(n, array2);
        heap->ChangeTabIntoHeap(10);
        heap->HeapSort(n,1);
        delete heap;
        clock_t t4 = clock();
        cout << "Czas wykonania HeapSort to: " << (double)(t4 - t3) / CLOCKS_PER_SEC << " sekundy" << endl;
        //BucketSort
        clock_t t5 = clock();
        Bucket_Sort_Int(array3, n, 10000000);
        ShortenedTabInt(array3, n);
        clock_t t6 = clock();
        cout << "Czas wykonania BucketSort to: " << (double)(t6 - t5) / CLOCKS_PER_SEC << " sekundy" << endl;
        delete[] array1, array2, array3;
    }
    cout << "STRUKTURY:" << endl;
    for (int o = 1; o <= MAX_ORDER; o++)
    {
        const int n = pow(10, o);
        cout << n << " Elementow w tablicy:" << endl;
        Struktura *array1 = new Struktura[n];
        for (int i = 0; i < n; i++)
        {
            Struktura nowy_obiekt;
            array1[i] = nowy_obiekt;
        }
        Struktura *array2 = new Struktura[n];
        memcpy(array2, array1, n * sizeof(Struktura));
        //HeapSort
        clock_t t1 = clock();
        Heap<Struktura> *heap = new Heap<Struktura>(n, array2);
        heap->ChangeTabIntoHeap(n);
        heap->HeapSort(n, 1);
        delete heap;
        clock_t t2 = clock();
        cout << "Czas wykonania HeapSort to: " << (double)(t2 - t1) / CLOCKS_PER_SEC << " sekundy" << endl;
        //BucketSort
        clock_t t3 = clock();
        Bucket_Sort_Templates(array2, n, 10000000);
        clock_t t4 = clock();
        cout << "Czas wykonania BucketSort to: " << (double)(t4 - t3) / CLOCKS_PER_SEC << " sekundy" << endl;
    }
}