Untitled

#include <iostream>
#include <string>
#include <chrono>
using namespace std;

// struktura simple_object
struct simple_object {

    string word;
    double key;

    friend ostream& operator<<(ostream& os, simple_object so);

};


// komparator dla simple_object
int simple_object_comparator(simple_object so1, simple_object so2) {
    if (so1.key == so2.key)
        return 0;
    else if (so1.key < so2.key)
        return -1;
    else if (so1.key > so2.key)
        return 1;
}

// Przeciążenia operatorów dla simple_object dla printowania
ostream& operator<<(ostream& os, simple_object so) { // CHUJ WIE
    string key = to_string(so.key);
    key.erase(key.find_last_not_of('0') + 1, string::npos);
    key.erase(key.find_last_not_of('.') + 1, string::npos);
    os << "Word: " + so.word + "; key: " + key + "\n";
    return os;
}

// Komparator - zgodnie z tym co w instrukcji, stworzony na potrzeby HeapSorta jako argument
int int_cmp(int i1, int i2) {
    if (i1 == i2)
        return 0;
    else if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return 1;
}

// heapSort
enum mode { BOTTOM_UP, TOP_DOWN }; // enumerator definiujacy czy kopiec ma byc tworzony od dolu czy od gory

template <typename T>
struct HeapSort {
    int size;
    T* heap_array;
    HeapSort(T* array, int n, int (*func)(T, T), bool mode = BOTTOM_UP) { // konstruktor (tablica, rozmiar, komparator, tryb) - i to jest wlasnie podpunkt z roszerzenia kopca
        heap_array = array; // uznajemy ze ta tablica to kopiec i dopiero ja bedziemy naprawiac, buduje kopiec z tej tablicy i dopiero potem sortuje

        if (mode == BOTTOM_UP) { // w razie czego sprawdzic czy nie pomylil krystian nazw !!!
            size = 0; // uznajemy ze tablica jest pusta mimo ze tak naprawde jest pelna
            for (int i = 0; i < n; i++) { // przy kazdej iteracji zwiekszamy (uznajemy ze jest o jeden wiekszy jest jej rozmiar)
                size++;
                heapUp(size, func); // tak jakby odkrywamy sobie po elemencie i robimy heap up
            }
        }
        else if (mode == TOP_DOWN) {
            size = n; // uznajemy ze jest pelna tablica (widzimy ja cala)
            for (int i = size / 2; i > -1; i--) { // idziemy od size/2 (taka zasada w heapie, bo ona nam pozwala na pominiecie liscie (ostatniego rzedu elementow))
                heapDown(i, func);
            }
        }

        sort(size, func); // konstruktor u mnie odrazu sortuje jakby sie przyprul skurwol zamaist tworzyc kopca i uzyc funkcje to dziala odrazu razem z tworzeniem kopca bo tak mi bylo wygodniej

    }

    // po stworzeniu kopca, idziemy od ostatniego elementu w tyl (przedostatni itd) oraz zawsze zamieniamy ostatni n-1 z pierwszym, zmniejszamy size (czyli potem ostatnim bedzie ten co chwile przed tym był przedostatnim) i robimy heap down, w zwiazku z czym po posortowaniu na samym dole (w lisciach kopca) bedziemy mieli najwieksze elementy
    void sort(int& size, int (*func)(T, T)) {
        for (int i = size - 1; i > 0; i--) {
            swap(heap_array[i], heap_array[0]); // jak cos to pomoc z neta (zawsze raczej bedzie wygldadac tak samo)
            size--;
            heapDown(0, func);
        }
    }

	// zwraca element z indeksem index
    T get(int index) {

        if (index < size) {
            return heap_array[index];
        }
    }

    // do wyliczania indeksów rodzica, lewego i prawego dziecka
    int parent(int i) {
        i++;
        return (i >> 1) - 1;
    }
    int left_child(int i) {
        i++;
        return (i << 1) - 1;
    }
    int right_child(int i) {
        i++;
        return (i << 1);
    }

    // przekopcowanie w góre (z poprzedniego zadania) - uzywane podczas tworzenia kopca wyzej w funkcji
    void heapUp(int el_index, int (*func)(T, T)) {
        if (func(heap_array[el_index], heap_array[parent(el_index)]) == 1 && el_index > 0) {
            T tmp = heap_array[parent(el_index)];
            heap_array[parent(el_index)] = heap_array[el_index];
            heap_array[el_index] = tmp;
            heapUp(parent(el_index), func);
        }
    }

	// do wyprintowania kopca
    string str(string(*func)(T), int k = -1) {
        return heap_array->str(func, k);
    }

    // przekopcowanie w dół (z poprzedniego zadania) - uzywane podczas tworzenia kopca wyzej w funkcji
    void heapDown(int el_index, int (*func)(T, T)) {

        int l_child_index = left_child(el_index);
        int r_child_index = right_child(el_index);

        int largest;
        if (l_child_index < size && func(heap_array[l_child_index], heap_array[el_index]) == 1)
            largest = l_child_index;
        else
            largest = el_index;

        if (r_child_index < size && func(heap_array[r_child_index], heap_array[largest]) == 1)
            largest = r_child_index;

        if (el_index != largest) {
            swap(heap_array[el_index], heap_array[largest]);
            heapDown(largest, func);
        }
    }
};



// count sort -> wykład 1:1, tak ma po prostu byc kazdy probably bedzie mial to samo
void countSort(int* arr, int size, int max) {
    int* array = new int[max] { 0 };

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

    int i = 0;
    for (int j = 0; j < max; j++) {
        while (array[j] > 0) {
            array[j]--;
            arr[i++] = j;
        }
    }

    delete[] array; 
}




// BucketSort
template <typename T>
struct Node {
    struct Node<T>* prev = nullptr;
    T data;
    struct Node<T>* next = nullptr;
};

template <typename T>
struct LinkedList {
    struct Node<T>* head = nullptr;
    struct Node<T>* tail = nullptr;
    int size = 0;

    T get(int i) {


        Node<T>* n = head;

        for (int j = 0; j < i; j++) {
            n = n->next;
        }

        return n->data;
    }

    void pushFront(T data) {

        // tworzenie węzła
        Node<T>* n = new Node<T>();
        n->data = data;

        n->next = head;

        // jeśli nie został wcześniej dodany żaden element
        if (head != nullptr) {
            head->prev = n;
        }
        else {
            tail = n;
            head = n;
        }

        head = n;

        // zwiększenie informacji o ilości elementów znajdujących się w liście
        size++;
    }

    // do wstawiania danych w odpowiednim miejscu w bucketsort
    void sortInsert(T data, int (*func)(T, T)) {
        if (head == nullptr || func(head->data, data) == 1 || func(head->data, data) == 0) {
            pushFront(data);
            return;
        }
        else if (func(tail->data, data) == -1 || func(tail->data, data) == 0) {
            pushBack(data);
            return;
        }


        Node<T>* current = head;

        while (current->next != nullptr && func(current->next->data, data) == -1) {
            current = current->next;
        }

        Node<T>* newNode = new Node<T>();
        newNode->data = data;
        newNode->next = current->next;
        current->next = newNode;

        size++;
    }


    void pushBack(T data) {

        // tworzenie węzła
        Node<T>* n = new Node<T>();
        n->data = data;

        n->prev = tail;

        // jeśli nie został wcześniej dodany żaden element
        if (tail != nullptr) {
            tail->next = n;
        }
        else {
            head = n;
            tail = n;
        }

        tail = n;

        // zwiększenie informacji o ilości elementów znajdujących się w liście
        size++;
    }

    void clear() {
        Node<T>* n = head;
        Node<T>* lastFound = nullptr;

        if (head == nullptr) {
            cout << "Lista nie zawiera żadnych elementów";
            return;
        }

        while (true) {
            lastFound = n;

            n = n->next;

            if (n == nullptr)
                break;

            delete n->prev;

            size--;
        }

        delete lastFound;

        // ustawienie tail i head na nullptr
        head = tail = nullptr;
    }

    int getSize() {
        return size;
    }
};

// BucketSort dla int
void bucketSort(int* arr, int size, int max) {

    int buckets = size;
	// do dzielenia kubelkow na czesci (rzutowanie na floata zeby nie bylo dzielenia calkowitego)
    int sep = ceil(max / (float)buckets); // może z internetu, na stronie geeksforgeeks byl wytlumaczone chyba, tylko trzeba zjechac na dol strony i pod kodem bedzie podział dla intow zamiast dla float chyba

    LinkedList<int>* array = new LinkedList<int>[buckets];
    int index;
    for (int i = 0; i < size; i++) {
        index = arr[i] / sep;
        array[index].sortInsert(arr[i], int_cmp);
    }

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

    int j = 0;
    for (int i = 0; i < buckets; i++) {
        int list_size = array[i].getSize();
        for (int k = 0; k < list_size; k++) {
            arr[j++] = array[i].get(k);
        }

        if (array[i].getSize())
            array[i].clear();
    }
    delete[] array;
}

// BucketSort dla reszty (to nie jest sortowanie w miejscu, z tych 3  tylkko heapsort jest)
template <typename T>
void bucketSort(T* arr, int size, double max, double (*func_k)(T), int (*func_cmp)(T, T)) {

    int buckets = size;

    // jest kubełkow tyle ile jest elementow w tablicy, zeby przy rozkladzie jakims jednostajnym wyszlo tak ze do kubelka trafi jedna liczba czyli nie bedzie trzeba sortowac kubelka (sortowanie w srodku ma byc jak najkrotsze, a w kubelku chcemy zeby bylo jak najmniej elementow)
    // najlepsze n+k, a najgorszy przypadek n^2
    LinkedList<T>* array = new LinkedList<T>[buckets];
    int index;
    double key;
    for (int i = 0; i < size; i++) {
        key = func_k(arr[i]); // funkcja ktora bierze klucz z obiektu
        index = min((int)(key / (max / buckets)), buckets - 1); // przydzielenie wartosci indeksu kubelka do ktorego ma trafic element z tablicy (kazdy kubelek to lista, a jak lista jednoelementowa to nie ma co sortowac prosciutto crudo)
        array[index].sortInsert(arr[i], func_cmp); // 1 sposob -> powkladac wszystko i posortowac, 2 sposob -> odrazu sie wklada do kubelka w miejscu w ktorym powinno byc (tutaj uzywamy 2 sposobu)
    } // po tym mam wszystkie juz elementy w kubelkach i kubelki sa posortowane

    // caly ten for odpowiada za wyciaganie z kubelkow do tablicy jako posortowane elementy
    int j = 0;
    for (int i = 0; i < buckets; i++) { // mamy pierwszy kubelek, w nim lista i iterujemy po kubelkach i z kazdego kubelka wyciagamy te elementy
        int list_size = array[i].getSize();
        for (int k = 0; k < list_size; k++) {
            arr[j++] = array[i].get(k); // dodawanie posortowanych elementow z kubelka do tablicy
        }

        if (list_size != 0)
            array[i].clear(); // czyszczenie listy
    }
    delete[] array; // zwalniamy pamiec

}

double simple_object_key_double(simple_object so) {
    return so.key;
}

 // EKSPERYMENTO DO INTÓW
//int main() {
//    const int MAX_ORDER = 7;
//    const int m = (int)pow(10, 7);
//
//    for (int o = 1; o <= MAX_ORDER; o++) {
//        const int n = (int)pow(10, o);
//        int* array1 = new int[n];
//
//        // Losowanie liczb
//        for (int i = 0; i < n; i++) {
//            array1[i] = rand() % m;
//        }
//
//        int* array2 = new int[n];
//        int* array3 = new int[n];
//        memcpy(array2, array1, n * sizeof(int));
//        memcpy(array3, array1, n * sizeof(int));
//
//        // Sortowanie przez zliczanie
//        auto t1 = std::chrono::high_resolution_clock::now();
//        countSort(array1, n, m);
//        auto t2 = std::chrono::high_resolution_clock::now();
//        auto counting_sort_duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
//
//        cout << "\nCounting sort czas: " << counting_sort_duration << " mikrosekund" << endl;
//        for (int i = 0; i < 10; i++) { // Pierwsze 10 elementów
//            cout << array1[i] << ", ";
//        }
//
//        // Sortowanie przez kopcowanie
//        t1 = std::chrono::high_resolution_clock::now();
//        HeapSort<int>* bh = new HeapSort<int>(array2, n, int_cmp, BOTTOM_UP);
//        t2 = std::chrono::high_resolution_clock::now();
//        auto heap_sort_duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
//
//        cout << "\nHeap sort czas: " << heap_sort_duration << " mikrosekund" << endl;
//        for (int i = 0; i < 10; i++) { // Pierwsze 10 elementów
//            cout << array2[i] << ", ";
//        }
//        delete bh;
//
//        // Sortowanie kubełkowe
//        t1 = std::chrono::high_resolution_clock::now();
//        bucketSort(array3, n, m);
//        t2 = std::chrono::high_resolution_clock::now();
//        auto bucket_sort_duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
//
//        cout << "\nBucket sort czas: " << bucket_sort_duration << " mikrosekund" << endl;
//        for (int i = 0; i < 10; i++) { // Pierwsze 10 elementów
//            cout << array3[i] << ", ";
//        }
//
//        // Sprawdzanie poprawności wyników sortowania
//        for (int i = 0; i < n; i++) {
//            if (array1[i] != array2[i] || array1[i] != array3[i]) {
//                cout << "Blad sortowania";
//                break;
//            }
//            if (i == n - 1)
//                cout << "\n\nSortowanie poprawne";
//        }
//
//        delete[] array1;
//        delete[] array2;
//        delete[] array3;
//    }
//}

// EKSPERYMENT DO RESZTY
int main() {
    const int MAX_ORDER = 7; // m a k s y m a l n y rzad w i e l k o s c i s o r t o w a n y c h danych
    const double m_double = (double)pow(2, 30); // m i a n o w n i k przy u s t a l a n i u losowej liczby

    for (int o = 1; o <= MAX_ORDER; o++) {
        const int n = (int)pow(10, o);

        simple_object* array1 = new simple_object[n];
        simple_object* array2 = new simple_object[n];

        for (int i = 0; i < n; i++) {
            array1[i].key = ((rand() << 15) + rand()) / m_double;
            array1[i].word = 'a' + rand() % 26; // obojetnie jakie bo i tak nie bierze udzial w niczym 
        }

        clock_t t1 = clock();
        HeapSort<simple_object>* bh = new HeapSort<simple_object>(array1, n, simple_object_comparator, TOP_DOWN);
        clock_t t2 = clock();

        cout << "\nHeap sort czas: " << (t2 - (double)t1) / CLOCKS_PER_SEC << endl;
        for (int i = 0; i < 10; i++)
            cout << array1[i] << ", ";

        t1 = clock();
        bucketSort(array2, n, 1.0, simple_object_key_double, simple_object_comparator);
        t2 = clock();

        // Sprawdzanie poprawności wyników sortowania
        //for (int i = 0; i < n; i++) {
        //    if (array1[i] != bh[i]) {
        //        cout << "Blad sortowania";
        //        break;
        //    }
        //    if (i == n - 1)
        //        cout << "\n\nSortowanie poprawne";
        //}

        delete[] array1;
        //delete[] bh;
		delete[] array2;

        // DZIAŁA HEAP SORT NIE DZIAŁA BUCKET SORT NIE WIADOMO CZEMU

    }
}


// int main()
// {
//     srand(time(NULL));

//     //int tablica[30];
//     //for (int i = 0; i < 30; i++)
//     //    tablica[i] = rand() % 100;

//     //cout << "Talibca: \n";
//     //for (int i = 0; i < 30; i++) {
//     //    cout << tablica[i] << ", ";
//     //}
//     //cout << "\n";


//     //countSort(tablica, 30, 100);
//     //bucketSort(tablica, 30, 100);


//     // HeapSort<int>* bh = new HeapSort<int>(tablica, 30, int_cmp, BOTTOM_UP);
//     //for (int i = 0; i < 30; i++)
//     //    cout << tablica[i] << ", ";

//     simple_object so_tab[]{ {"marcin9", 10.}, {"marcin1", 0.87}, {"marcin3", 1.87}, {"marcin0", 0.00568}, {"marcin4", 2.33},{"marcin10", 10.008}, {"marcin6", 5.18}, {"marcin2", 1.07}, {"marcin5", 3.33}, {"marcin8", 9.33}, {"marcin7", 8.1} };
//     bucketSort(so_tab, 11, 11, simple_object_key, simple_object_comparator);
//     for (int i = 0; i < 11; i++)
//         cout << so_tab[i];
// }