#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <time.h>


using namespace std;

const int iloscElementow=10;


struct ulamki
{
    float licznik;
    float mianownik;
};

void losuj(ulamki zbior[])
{
    int i=0;
    srand( time( NULL ) );
    for(i=0;i<iloscElementow;++i)
    {
        zbior[i].licznik=rand()+1;
        zbior[i].mianownik=rand()+1;

    }
	cout<<"Wylosowano "<<iloscElementow<<" elementow"<<endl;
    }

float wynik (ulamki element)
{
	return element.licznik/element.mianownik;
}




void BubbleSort(ulamki * t, int n)
{
   int i,j;
   ulamki temp;
   bool czy_posortowana = true;

   for (j=0;j<n-1;j++){
      czy_posortowana = true;
      for (i=0;i<n-1-j;i++)
         if (wynik(t[i])>wynik(t[i+1]))
         {
            czy_posortowana = false;
            temp = t[i+1]; // zamiana elementow
            t[i+1] = t[i];
            t[i] = temp;
         }
         if (czy_posortowana == true) return;
   }
}

void InsertionSort(ulamki *t, int n)
{
   int i, j;
   ulamki temp;
   for (i=1;i<n;i++)
   {
      temp = t[i];
      j = i-1;
      while (j>=0 && wynik(t[j]) > wynik(temp))
      {
         t[j+1]=t[j];
         j--;
      }
      t[j+1]=temp;
   }
}

void Merge(ulamki *t,int p, int sr, int k)
{
   int i=sr+1,j=p,x=0,q=p;
   static ulamki tempTab[iloscElementow];

   for (x=p;x<=k;x++)
      tempTab[x] = t[x];

   while (j<=sr && i<=k){
      if (wynik(tempTab[j])>wynik(tempTab[i]))
         t[q++]=tempTab[i++];
      else
         t[q++]=tempTab[j++];
   }

   while (j<=sr) t[q++]=tempTab[j++];
}

void MergeSort(ulamki *t, int p, int k)
{
   int sr = (p+k)/2;
   if (p<k) {
      MergeSort(t,p,sr);
      MergeSort(t,sr+1,k);
      Merge(t,p,sr,k);
   }
}

void QuickSort(ulamki *t, int left, int right)
{
     int i=left;
     int j=right;
     ulamki x=t[(left+right)/2];
     do{
         while(wynik(t[i])<wynik(x)) i++;
         while(wynik(t[j])>wynik(x)) j--;
         if(i<=j){
             ulamki temp=t[i];
             t[i]=t[j];
             t[j]=temp;
             i++;
             j--;
         }
     }while(i<=j);
     if(left<j) QuickSort(t,left,j);
     if(right>i) QuickSort(t,i,right);
}



int _tmain(int argc, _TCHAR* argv[])
{
	static ulamki dane[iloscElementow];
	static ulamki kopia[iloscElementow];
	unsigned long long start;
	unsigned long long koniec;
	int i;
	losuj(dane);
	//BubbleSort
	memcpy(kopia, dane, sizeof(ulamki) * iloscElementow );//tworzenie kopii
	start = clock();
	BubbleSort(kopia,iloscElementow);
	koniec =clock() - start;
	cout<<"Bubblesort dla "<<iloscElementow<<" trwal "<<koniec<<" ms"<<endl;

	//InsertionSort
	memcpy(kopia, dane, sizeof(ulamki) * iloscElementow);
	start = clock();
	InsertionSort(kopia,iloscElementow);
	koniec =clock() - start;
	cout<<"Insertion Sort dla "<<iloscElementow<<" trwal "<<koniec<<" ms"<<endl;


	//MergeSort
	memcpy(kopia, dane, sizeof(ulamki) * iloscElementow);
	start = clock();
	MergeSort(kopia,0,iloscElementow-1);
	koniec =clock() - start;
	cout<<"Merge Sort dla "<<iloscElementow<<" trwal "<<koniec<<" ms"<<endl;



	//QuickSort
	memcpy(kopia, dane, sizeof(ulamki) * iloscElementow);
	start = clock();
	QuickSort(kopia,0,iloscElementow-1);
	koniec =clock() - start;
	cout<<"Quick Sort dla "<<iloscElementow<<" trwal "<<koniec<<" ms"<<endl;
	/*for(i=0;i<iloscElementow;++i)
	{
		cout<<kopia[i].licznik/kopia[i].mianownik<<endl;
	}*/

	return 0;
}