#include <stdio.h>
#include <stdlib.h>
#include <time.h>


void kopiuj_tablice(int tab[], int tab2[], int rozmiar){

    for (int i=0; i < rozmiar; i++)
    {
        tab2[i]=tab[i];
    }

}


void zmiana(int tab[], int lewy, int prawy)
{

    int chwilowy = tab[lewy];
    tab[lewy] = tab[prawy];
    tab[prawy] = chwilowy;

}

void drukujTablice(int tab[], int dlug)
{

    for (int i=0; i<dlug; i++)
    {
        printf("%d ", tab[i]);
    }


}


int partition(int tab[], int lewy, int prawy)
{

    int chwilowo = 0;
    int x = tab[prawy];
    int i = lewy - 1;
    for (int j=lewy; j<=prawy; j++)
    {
        if(tab[j] <= x)
        {
            i++;
            chwilowo = tab[i];
            tab[i] = tab[j];
            tab[j] = chwilowo;
        }

    }

    if(i<prawy){ return i;}
    else { return i-1; }

}


void quicksort(int tab[], int lewy, int prawy){

    if (lewy < prawy)
    {

        int part = partition(tab,lewy,prawy);
        quicksort(tab, lewy, part - 1);
        quicksort(tab, part + 1 ,prawy);

    }


}

/*
void wstawianie_sort(int tab[], int rozmiar)
{

    //printf("dzialam insert\n");
    int element_sprawdzany;
    int indeks_elementu_po_lewej;
    for (int i = 1; i < rozmiar; i++)
    {

        element_sprawdzany = tab[i];
        indeks_elementu_po_lewej = i-1;


        while ( indeks_elementu_po_lewej >= 0 && tab[indeks_elementu_po_lewej] > element_sprawdzany )
        {
            printf("dzialam insert srodek\n");
            tab[indeks_elementu_po_lewej+1] = tab[indeks_elementu_po_lewej];
            indeks_elementu_po_lewej = indeks_elementu_po_lewej - 1;

        }

        tab[indeks_elementu_po_lewej + 1] = element_sprawdzany;


    }

}*/

void wstawianie_sort(int tab[], int rozmiar){

    int i,klucz,j;
    for(i=1; i < rozmiar; i++){

        klucz = tab[i];
        j = i - 1;
        //printf("dzialam");

        while (j >= 0 && tab[j] > klucz){
            tab[j+1] = tab[j];
            j = j - 1;
            //printf("dzialam wewnatrz");

        }
    tab[j + 1] = klucz;

    }


}








void quicksort_zepsuty(int tab[], int lewy, int prawy, int rozmiar, int c){

    if (lewy < prawy)
    {

        //printf("dzialam srodek\n");
        if ( (prawy - lewy + 1) > c )
        {

            //printf("działam wnatrz\n");

        int part = partition(tab,lewy,prawy);
        quicksort(tab, lewy, part);
        quicksort(tab, part + 1 ,prawy);

        }


    }

 }







int main(){

    srand(time(NULL));

    int dlugosc = 10000;

    int tablica[dlugosc]; // <--- Losowe
    int tablica2[dlugosc];
    int tablica3[dlugosc]; // <--- losowe
    int tablica4[dlugosc];

    int limit = 500;

   // int dlugosc = sizeof(tablica)/sizeof(tablica[0]);

    for(int i=0; i> dlugosc; i++)
    {

        tablica[i] = rand() % 101;
        tablica2[i] = dlugosc - i;

    }


    for(int i=0; i>dlugosc; i++){

        tablica3[i]=tablica[i];
        tablica4[i] = dlugosc - 1;


    }


    // SPRAWDZAMY DLA NORMALNEGO QUICKSORTA LOSOWE DANE

    clock_t poczatek = clock();
    quicksort(tablica,0,dlugosc-1);
    clock_t koniec = clock();
    printf("Czas dla quicksorta zywklego z danymi losowymi = %lfs\n", (koniec - poczatek) / 1000000.0);


    // SPRAWDZAMY DLA ZEPSUTEGO QUICKSORTA LOSOWE DANE

    poczatek = clock();
    quicksort_zepsuty(tablica3,0,dlugosc-1,dlugosc,limit);
    wstawianie_sort(tablica3,dlugosc);
    koniec = clock();
    printf("Czas dla zepsutego quicksorta z danymi losowymi = %lfs\n", (koniec - poczatek) / 1000000.0);


    // SPRAWDZAMY DLA NORMALNEGO QUICKSORTA NIEKORZYSTNE DANE

    poczatek = clock();
    quicksort(tablica2,0,dlugosc-1);
    koniec = clock();
    printf("Czas dla quicksorta zywklego z niekorzystnymi danymi = %lfs\n", (koniec - poczatek) / 1000000.0);

    // SPRAWDZAMY DLA ZEPSUTEGO QUICKSORTA NIEKORZYSTNE DANE

    poczatek = clock();
    quicksort_zepsuty(tablica4,0,dlugosc-1,dlugosc,limit);
    wstawianie_sort(tablica4,dlugosc);
    koniec = clock();
    printf("Czas dla zepsutego quicksorta z niekorzystnymi danymi = %lfs\n", (koniec - poczatek) / 1000000.0);



    //int tablica[] = {19,28,37,46,56,412,1,6,9,11};

    //int piwot = tablica[rand()%dlugosc];

    //printf("Nasza tablica \t\t: ");

    //drukujTablice(tablica,dlugosc);


    //printf("\nNasz startowy pivot \t: %d\n", piwot);

    /*
    quicksort(tablica,0,dlugosc-1);

    printf("\nTablica posortowana\t: ");

    drukujTablice(tablica,dlugosc);

    printf("\n");
    */



    printf("============================================================\n");


    int tab5[dlugosc];

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

        tab5[i] = rand() % 101;

    }
    poczatek = clock();
    quicksort_zepsuty(tab5,0,dlugosc-1,dlugosc,limit);
    wstawianie_sort(tab5,dlugosc);
    //quicksort_zepsuty(tablica_kopia,0,dlugosc-1,dlugosc,limit);
    //wstawianie_sort(tablica_kopia,dlugosc);
    koniec = clock();
    printf("Czas dla zepsutego quicksorta z niekorzystnymi danymi = %lfs\n", (koniec - poczatek) / 1000000.0);


    /*
    quicksort_zepsuty(tablica,0,dlugosc-1,dlugosc,5);

    printf("\nTablica posortowana\t: ");

    drukujTablice(tablica,dlugosc);

    printf("\n");
    */


    return 0;

}