#include <iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<time.h>
#include<fstream>
#include<chrono>
#define LEWY(w) ((2)*(w))
#define PRAWY(w) ((w)*2 +1)

using namespace std;


int licznik_operacji = 0;


void losowe_liczby_increase(int n, int *tab, int k);

bool malejaco(int a, int b);

void losowe_liczby_decrease(int n, int *tab, int k);

void losowe_liczby_V(int n, int *tab, int k);

void losowe_liczby_A(int n, int *tab, int k);

void losowe_liczby_los(int n, int *tab, int k);



void shell_sort_shell(int *a, int rozmiar)
{
    porownania = 0;
    zamiana = 0;
    int przeskok = rozmiar / 2;
    while (przeskok >= 1)
    {
        insertion_sort_shell(a, rozmiar, przeskok);
        przeskok /= 2;
    }
}
void shell_sort_knuth(int *a, int rozmiar)
{
    porownania = 0;
    zamiana = 0;
    int przeskok;
    for (przeskok = 1; przeskok < rozmiar; przeskok = przeskok * 3 + 1);
    przeskok /= 9;
    if (!przeskok)
        przeskok++;
    while (przeskok > 0)
    {
        insertion_sort_shell(a, rozmiar, przeskok);
        przeskok /= 3;
    }
}
void insertion_sort_shell(int *a, int rozmiar, int przeskok)
{
    int buff, j;
    for (int i = przeskok; i < rozmiar; i++)
    {
        buff = a[i];
        licznik_operacji++;
        for (j = i; j >= przeskok && a[j - przeskok] > buff; j -= przeskok, licznik_operacji++;)
        {
            a[j] = a[j - przeskok];
            licznik_operacji++;

        }

        a[j] = buff;
        zamiana++;
    }
}




void scal(int dol, int srodek, int gora, int *tab, int * pom) {//w merge sorcie wpisujemy dane do pomocniczej tablicy wiec nie ma defacto zamiany el stad nalezy liczyc il operacji przypisania do tablicy wynikowej
    int i = dol, j = srodek + 1;
    for (int k = dol; k <= gora; k++) //n operacji przypisania
    {
        pom[k] = tab[k];
        licznik_operacji++;
    }

    for (int k = dol; k <= gora; k++) {// co najmniej n operacji porownan(c*n) + n operacji przypisan//gdzie c jest stala
        licznik_operacji++;
        if (i <= srodek) {
            licznik_operacji++;
            if (j <= gora) {
                licznik_operacji++;
                if (pom[j] > pom[i]) {
                    tab[k] = pom[j++];
                    licznik_operacji ++;
                }
                else
                    tab[k] = pom[i++];
                licznik_operacji++;
            }
            else
                tab[k] = pom[i++];
            licznik_operacji++;
        }
        else
            tab[k] = pom[j++];
        licznik_operacji++;
    }
}

void Merge_sort(int dol, int gora, int *tab, int * pom) {
    licznik_operacji++;
    if (gora <= dol)  return;
    Merge_sort(dol, (dol + gora) / 2, tab, pom);
    Merge_sort((dol + gora) / 2 + 1, gora, tab, pom);

    scal(dol, (gora + dol) / 2, gora, tab, pom);
}




void restore_heap(int n, int *tab, int  wezel) {//n to jest heap size
    int smallest;
    int  l = LEWY(wezel);
    int p = PRAWY(wezel);
    licznik_operacji += 2;
    if (l<n && tab[l] <tab[wezel]) //lewy
    {
        smallest = l;
    }
    else
    {
        smallest = wezel;
    }
    licznik_operacji ++;
    if (p<n && tab[p] <tab[smallest])
    {
        smallest = p;
        licznik_operacji++;

    }
    swap(tab[wezel], tab[smallest]);
    licznik_operacji += 2;
    if (smallest != wezel)
        restore_heap(n, tab, smallest);

}
void zbuduj_heap(int n, int *tab) {

    for (int i = n / 2; i > 0; i--)
    {
        restore_heap(n, tab, i);
    }

}

void heap_sort(int *tab, int n) {//na potrzeby heap sort nalezy indeksowac od i =1 do n

    zbuduj_heap(n, tab);
    n -= 1;
    for (int i = n; i > 1; i--) {
        swap(tab[1], tab[i]);
        n -= 1;
        restore_heap(n, tab, 1);
    }

}



void quick_sort(int tab[], int dol, int gora) {//pivotem pierwszy el tablicy
    licznik_operacji++;
    if (gora <= dol) { return; }
    int pivot = tab[dol];
    //cout << pivot << endl;///////////////////////wypisz wartosc pivota w kazdym wywolaniu
    int j = gora + 1, i = dol - 1;

    while (1) {

        while (pivot < tab[++i]) { licznik_operacji++; };


        while (pivot > tab[--j]) { licznik_operacji++; };

        if (j >= i) {
            swap(tab[i], tab[j]); licznik_operacji ++;

        }
        else { break; }
    }

    if (j > dol) { quick_sort(tab, dol, j); }
    if (i < gora) { quick_sort(tab, i, gora); }
}