#include <algorithm>
#include <iostream>
#include <time.h>
#include <vector>
#include <windows.h>
#include "klasa.h"
using namespace std;
int ilosc;

vector < wymierna> liczba,liczba2;
void wpisz()
{
    unsigned long long int calkowita;
    unsigned long long int licznik;
    unsigned long long int mianownik;
    unsigned long long int niewlasciwa;
    cout<<"Podaj ilosc tych liczb: "<<endl;
    cin>>ilosc;
    srand(time(0));
    for(int i=0;i<ilosc;i++)
    {
        calkowita=(rand()%100) * RAND_MAX + rand();
        licznik=(rand()%100) * RAND_MAX + rand();
        mianownik=(rand()%100) * RAND_MAX + rand()+1;
        niewlasciwa=(calkowita*mianownik)+licznik;
        if(i>16)
                mianownik=200;
        liczba.push_back(wymierna(calkowita,licznik,mianownik,niewlasciwa));
    }
	liczba2=liczba;
}
void wypisz()
{
    for( int i = 0; i < liczba.size(); i++ )
    {
        cout << endl;
        cout << "Licznik: " << liczba[i].licznik << endl;
        cout << "Calkowita["<<i<<"]: "<<liczba[i].calkowita<<endl;
        cout << "Mianownik: " <<liczba[i].mianownik << endl;
    }
}
void wypisz2()
{
    cout<<"\nposortowane:"<<endl;
    for(int i=0;i<liczba.size(); ++i )
    {
		cout << endl;
		cout << "Niewlasciwa: " << liczba[i].niewlasciwa << endl;
		cout << "Mianownik: " <<liczba[i].mianownik << endl;
    }
}
void sortowaniesortem()
{
    sort(liczba.begin(), liczba.end(),mniejszy);
    sort(liczba.begin(),liczba.end(),mniejsiejszy);
}
double GetTime()
{
	long long f,t;
	QueryPerformanceFrequency((PLARGE_INTEGER)&f);
	QueryPerformanceCounter((PLARGE_INTEGER)&t);
	return (double)t/(double)f;
}
void mergesort(int pocz, int kon)
{
	int sr;
	if (pocz<kon)
	{
		sr=(pocz+kon)/2;
		mergesort(pocz, sr);    // Dzielenie lewej części
		mergesort(sr+1, kon);   // Dzielenie prawej części
		merge(pocz, sr, kon);   // Łączenie części lewej i prawej
	}
}
void merge(int pocz, int sr, int kon)
{
	vector<wymierna> t;
	int i,j,q;
	t=liczba2;  // Skopiowanie danych do tablicy pomocniczej
	i=pocz; j=sr+1; q=pocz;                 // Ustawienie wskaźników tablic
	while (i<=sr && j<=kon)
	{         // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej
		if (t[i].mianownik<t[j].mianownik)
			liczba2[q++].mianownik=t[i++].mianownik;
		else
			liczba2[q++].mianownik=t[j++].mianownik;
	}
	while (i<=sr)
		liczba2[q++].mianownik=t[i++].mianownik; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył
}

int main()
{
    wpisz();
    double czas1=0,czas2=0;
    double start=GetTime(); //(*)
    sortowaniesortem();
    double koniec=GetTime(); //(**)
    czas1=koniec-start;
	start=GetTime();
	mergesort(0,ilosc);
	koniec=GetTime();
    cout <<"          czas sorta:"<<czas1<<endl;
    cout <<"czas wlasnej funkcji:"<<czas2<<endl;
    system("PAUSE");
    return 0;
}