#include <iostream>
#include <clocale>
#include <cstdlib>
#include <ctime>

using std::string;

void quickSort(int*, int, int);
void bubbleSort();
void countingSort(int*, int*, int, int&);
void insertionSort(int*, int&);
void mergeSort(int, int, int*, int*);

int maxNumber(int*, int&);

int main() {
    setlocale(LC_ALL, "polish");
    srand(time(NULL));

    int usrCh = 0;

    const int tabSize = 7;
    string choices[tabSize] = {
        "Bubble sort",
        "Quick sort",
        "Counting sort",
        "Insertion sort",
        "Heapsort",
        "Shell sort",
        "Merge sort"
    };

    for (int i = 0; i < tabSize; ++i)
        std::cout << i+1 << ". " << choices[i] << std::endl;

    std::cout << "Twój wybór: ";
        std::cin >> usrCh;

    switch(usrCh) {
        case 1: {

            bubbleSort();

            break;
        }
        case 2: {

            int howMuch = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            quickSort(tab, 0, howMuch-1);
            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            break;
        }
        case 3: {

            int howMuch = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];
            int tab2[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            int maxNum = maxNumber(tab, howMuch);
            countingSort(tab, tab2, maxNum, howMuch);
            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab2[i] << std::endl;

            break;
        }
        case 4: {

            int howMuch = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            insertionSort(tab, howMuch);
            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            break;
        }
        case 5: {

            int howMuch = 0;
            int buffX = 0, buffY = 0, buffZ = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            for (int i = 1; i < howMuch; ++i) {
                buffX = tab[i];
                buffY = i;

                while (1) {
                    buffZ = buffY;
                    buffY = (buffZ - 1) / 2;

                    if ((buffZ == 0) || (tab[buffY] >= buffX)) break;
                    tab[buffZ] = tab[buffY];
                }

                tab[buffZ] = buffX;
            }

            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            break;
        }
        case 6: {

            int howMuch = 0, iterI = 0, iterJ = 0, iterH = 0;
            int buffX = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            for (iterH = 1; iterH < howMuch; iterH = 3*iterH+1);
            iterH /= 9;
            if (!iterH) iterH++;

            while (iterH) {
                for (iterJ = howMuch-iterH-1; iterJ >= 0; --iterJ) {
                    buffX = tab[iterJ];
                    iterI = iterJ + iterH;
                    while ((iterI < howMuch) && (buffX > tab[iterI])) {
                        tab[iterI - iterH] = tab[iterI];
                        iterI += iterH;
                    }
                    tab[iterI - iterH] = buffX;
                }
                iterH /= 3;
            }

            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            break;
        }

        case 7: {

            int howMuch = 0;

            std::cout << "Ile liczb chcesz losować: ";
                std::cin >> howMuch;
            int tab[howMuch];
            int tab2[howMuch];

            for (int i = 0; i < howMuch; ++i)
                tab[i] = rand()%1000+1;

            std::cout << "Wylosowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab[i] << std::endl;

            mergeSort(0, howMuch-1, tab, tab2);
            std::cout << "Posortowane liczby to: " << std::endl;
            for (int i = 0; i < howMuch; ++i)
                std::cout << i+1 << ". " << tab2[i] << std::endl;

            break;
        }

        default: {
            return 1;
        }
    }

    return 0;
}

void quickSort(int tab[], int left, int right) {

    int firstIterator = left;
    int secondIterator = right;
    int center = tab[(left+right) / 2];

    while (firstIterator <= secondIterator) {
        while (tab[firstIterator] < center)
            firstIterator++;

        while (tab[secondIterator] > center)
            secondIterator--;

        if (firstIterator <= secondIterator) {
            std::swap(tab[firstIterator], tab[secondIterator]);

            firstIterator++;
            secondIterator--;
        }

    }

    if (left < secondIterator) quickSort(tab, left, secondIterator);
    if (right > firstIterator) quickSort(tab, firstIterator, right);

    return;
}

void bubbleSort() {

        // bubble sort
        int howMuch = 0;

        std::cout << "Ile liczb chcesz losować: ";
        std::cin >> howMuch;
        int tab[howMuch];

        for (int i = 0; i < howMuch; ++i)
            tab[i] = rand()%1000+1;

        std::cout << "Wylosowane liczby to: " << std::endl;
        for (int i = 0; i < howMuch; ++i)
            std::cout << i+1 << ". " << tab[i] << std::endl;

        // sortowanie
        for (int i = 0; i < howMuch; ++i) {
            for (int j = 0; j < howMuch-1; ++j) {
                if (tab[j] > tab[j+1]) std::swap(tab[j], tab[j+1]);
             }
         }

        std::cout << "Posortowane liczby to: " << std::endl;
        for (int i = 0; i < howMuch; ++i)
            std::cout << i+1 << ". " << tab[i] << std::endl;

    return;
}

void countingSort(int mainTab[], int secondTab[], int maxNum, int &howMuch) {

    int statTab[maxNum+1];

    for (int i = 0; i <= maxNum; ++i)
        statTab[i] = 0;

    for (int i = 0; i < howMuch; ++i)
        statTab[(mainTab[i])]++;

    for (int i = 1; i <= maxNum; ++i)
        statTab[i] += statTab[i-1];

    for (int i = howMuch-1; i >= 0; --i) {
        secondTab[(statTab[(mainTab[i])])-1];
        statTab[(mainTab[i])]--;
    }

    return;
}

int maxNumber(int tab[], int &howMuch) {

    int max = tab[0];
    for (int i = 1; i < howMuch; --i) {
        if (max < tab[i]) max = tab[i];
    }

    return max;
}

void insertionSort(int tab[], int &howMuch) {

    int insert = 0, j = 0;

    for (int i = 0; i < howMuch; ++i) {

        insert = tab[i];
        j = i - 1;

        while (j >= 0 && tab[j] > insert) {
            tab[j+1] = tab[j];
            --j;
        }

        tab[j+1] = insert;
    }

    return;
}

void mergeSort(int first, int last, int tab[], int tab2[]) {

    int oldFirst = 0;
    int it1 = 0, it2 = 0;

    oldFirst = (first + last + 1) / 2;
    if (oldFirst - first > 1) mergeSort(first, oldFirst - 1, tab, tab2);
    if (last - oldFirst > 0) mergeSort(oldFirst, last, tab, tab2);

    it1 = first; it2 = last;
    for (int i = first; i <= last; ++i)
        tab2[i] = ((it1 == oldFirst) || ((it2 <= last) && (tab[it1] > tab[it2]))) ? tab[it2++] : tab[it1++];
    for (int i = first; i <= last; ++i)
        tab[i] = tab2[i];

    return;
}