#include "stdafx.h"
#include <intrin.h> // biblioteka potrzebna do zliczania cykli procesora
#include <malloc.h>
#include <stdlib.h>

/* Opis bardziej szczegolowy ponizszego programu :
- funkcja main programu odpowiada tylko i wylacznie za uruchomienie poszczegolnych funkcji sortowania oraz wyswietlenie informacji o czasie ich wykonania
- poszczegolne funkcje sortujace wykonuja nastepujace dzialania :
	- wczytuja plik z danymi wejsciowymi (input.txt), jesli nie istnieje, wywalaja blad
	- tworza WLASNA, LOKALNA tablice danych wejsciowych i sortuja je wedlug odpowiednich algorytmow (opisane w poszczegolnych funkcjach)
	- zapisuja plik z posortowanymi danymi do pliku o rozszerzeniu .txt i nazwie odpowiedniej do stosowanego algorytmu
	- zamykaja otwarte pliki i zwalniaja zajeta pamiec

Na pewno nie jest to najlepszy program z tych przyslanych do Pana, pewnie nie jest nawet dobry - w koncu jest proporcjonalny
do moich umiejetnosci, ale jestem z niego dumny, bo zajal mi niemalo czasu i dziala jak nalezy. ;)
-D.K. */

// std::swap jest beznadziejne

unsigned __int64 BubbleSort()
{
	FILE * dane_bubblesort; // tworzymy zmienna plikowa, do ktorej zostana wczytane dane do posortowania
	dane_bubblesort=fopen("input.txt","r"); // otwieramy plik z danymi
	if(dane_bubblesort==NULL) // jesli plik nie istnieje, wywalamy komunikat i konczymy program
	{
		printf("Blad pliku.");
		exit;
	}
	int *tablica_bubblesort; // tworzymy wskaznik na tablice
	tablica_bubblesort=(int*)malloc(99999*sizeof(int)); // alokujemy pamiec dla tablicy
	if(tablica_bubblesort==NULL) // jesli nie udalo sie zaalokowac pamieci, wywalamy komunikat i konczymy program
	{
		printf("Blad pamieci.");
		exit;
	}
	for(int i=0;i<99999;i++) // wypelniamy tablice danymi wczytanymi z pliku
	{
		fscanf(dane_bubblesort,"%d\n",&tablica_bubblesort[i]);
	}
	fclose(dane_bubblesort); // zamykamy plik i zapominamy o nim
	int buf=0; // tworzymy zmienna pomocnicza dla algorytmu sortujacego (w tym przypadku bufor do przenoszenia danych)
	unsigned __int64 przed_bubblesort; // tworzymy zmienna sluzaca do pomiaru ilosci cykli procesora
	przed_bubblesort=__rdtsc(); // przypisujemy utworzonej zmiennej wartosc odpowiadajaca ilosci cykli przed rozpoczeciem algorytmu sortujacego
	for(int i=0;i<99999;i++) // implementacja sortowania babelkowego - startujemy petle sprawdzajaca kazdy element tablicy
	{ 
		for(int j=99998;j>=i;j--) /* startujemy druga petle (dekrementacyjna, bo tak latwiej jest zamieniac wyrazy w tablicy), ktora sprawdza
								  wszystkie elementy petli oprocz tych juz sprawdzonych (stad warunek kontynuowania : j>=i) */
		{
			if(tablica_bubblesort[j-1]>tablica_bubblesort[j]) // porownujemy kazde kolejne dwa sasiadujace wyrazy
			{ // i jesli jest spelniony warunek, ze jeden z nich jest wiekszy, zamieniamy je miejscami
				buf=tablica_bubblesort[j-1];
				tablica_bubblesort[j-1]=tablica_bubblesort[j];
				tablica_bubblesort[j]=buf;
			}
		}
	}
	unsigned __int64 po_bubblesort; // tworzymy zmienna, w ktorej zostanie zapisana ilosc cykli procesora po wykonaniu algorytmu sortujacego
	po_bubblesort=__rdtsc(); // do przed chwila utworzonej zmiennej przypisujemy wartosc odpowiadajaca ilosci cykli procesora
	FILE * bubblesort; // tworzymy zmienna plikowa, do ktorej zapiszemy wyniki sortowania
	bubblesort=fopen("bubblesort.txt","w"); // otwieramy plik do zapisu wynikow w trybie write
	if(bubblesort==NULL) // jesli pliku nie udalo sie otworzyc (co w sumie byloby dziwne), wywalamy komunikat i konczymy program
	{
		printf("Blad pliku.");
		exit;
	}
	for(int i=0;i<99999;i++) // wypelniamy plik wartosciami z posortowanej juz tablicy
	{
		fprintf(bubblesort,"%d\n",tablica_bubblesort[i]);
	}
	fclose(bubblesort); // zamykamy plik z wynikami i zapominamy o nim
	free(tablica_bubblesort); // zwalniamy pamiec zajeta przez tablice z wynikami
	return (po_bubblesort-przed_bubblesort); // jako wartosc zwracana przez funkcje zwracamy ilosc cykli potrzebnych do wykonania algorytmu sortujacego
}

unsigned __int64 InsertSort()
{
	/* wiele z instrukcji napotkanych tutaj jest analogiczna do tych z poprzedniej funkcji, tak wiec komentowane beda tylko te czesci,
	ktore sie znacznie roznia - m. in. algorytm sortowania */
	FILE * dane_insertsort;
	dane_insertsort=fopen("input.txt","r");
	if(dane_insertsort==NULL)
	{
		printf("Blad pliku.");
		exit;
	}
	int *tablica_insertsort;
	tablica_insertsort=(int*)malloc(99999*sizeof(int));
	if(tablica_insertsort==NULL)
	{
		printf("Blad pamieci.");
		exit;
	}
	for(int i=0;i<99999;i++)
	{
		fscanf(dane_insertsort,"%d\n",&tablica_insertsort[i]);
	}
	fclose(dane_insertsort);
	unsigned __int64 przed_insertsort;
	int temp,j; /* tworzymy (nie inicjujemy, bo nie ma po co - i tak zaraz zostanie nadpisana) zmienna pomocnicza dla algorytmu sortujacego,
				w tym przypadku jest to zmienna, do ktorej tymczasowo kopiujemy wartosc z serii danych, ktora w danym momencie uwazamy za
				najmniejsza oraz licznik do petli zagniezdzonej */
	przed_insertsort=__rdtsc();
	for(int i=1;i<99999;i++) // implementacja sortowania przez wstawianie
	{
		temp=tablica_insertsort[i]; // wybieramy dowolny element ze zbioru nieuporzadkowanego (w tym przypadku jest to drugi element)
		for(j=i-1;(j>=0) && (tablica_insertsort[j]>temp);j--) // porownujemy go z kolejnymi elementami zbioru nieuporzadkowanego
		{
			tablica_insertsort[j+1]=tablica_insertsort[j]; /* i wstawiamy w kolejne miejsca tablicy uporzadkowanej, dopoki nie sa one wieksze od wartosci
														   wybranej przez poprzednia petle */
		}
		tablica_insertsort[j+1]=temp; // przesuwamy element losowy (czyli najwiekszy z tych, ktore zdazylismy porownac) w gore zbioru
	}
	unsigned __int64 po_insertsort;
	po_insertsort=__rdtsc();
	FILE * insertsort;
	insertsort=fopen("insertsort.txt","w");
	if(insertsort==NULL)
	{
		printf("Blad pliku.");
		exit;
	}
	for(int i=0;i<99999;i++)
	{
		fprintf(insertsort,"%d\n",tablica_insertsort[i]);
	}
	fclose(insertsort);
	free(tablica_insertsort);
	return(po_insertsort-przed_insertsort);
}

unsigned __int64 ChoiceSort()
{
	FILE * dane_choicesort;
	dane_choicesort=fopen("input.txt","r");
	if(dane_choicesort==NULL)
	{
		printf("Blad pliku.");
		exit;
	}
	int *tablica_choicesort;
	tablica_choicesort=(int*)malloc(99999*sizeof(int));
	if(tablica_choicesort==NULL)
	{
		printf("Blad pamieci.");
		exit;
	}
	for(int i=0;i<99999;i++)
	{
		fscanf(dane_choicesort,"%d\n",&tablica_choicesort[i]);
	}
	fclose(dane_choicesort);
	unsigned __int64 przed_choicesort;
	int buf=0; // pierwsza ze zmiennych pomocniczych - bufor do zamieniania miejscami wyrazow tablicy
	int indeks_min; // druga ze zmiennych pomocniczych - indeks wyrazu, ktorego chcemy znalezc (maslo maslane, ale nie wiem jak to inaczej wytlumaczyc)
	przed_choicesort=__rdtsc();
	for(int h=0;h<99999;h++) // implementacja sortowania przez wybor
	{
		indeks_min=h; // przypisujemy licznik petli do zmiennej identyfikujacej indeks wyrazu "szukanego"
		for(int i=h+1;i<99999;i++) // startujemy druga petle, ktora szuka wyrazu na zastapienie wyrazu "szukanego"
		{
			if(tablica_choicesort[i]<tablica_choicesort[indeks_min]) indeks_min=i; /* jesli znaleziony zostanie wyraz, ktorego wartosc jest mniejsza od
																				   wyrazu pierwszego (ktory ma byc najmniejszy), przypisujemy jej indeks
																				   do zmiennej wyrazajacej indeks "szukanego" wyrazu */
		}
		buf=tablica_choicesort[h]; // zamieniamy miejscami elementy tabeli
		tablica_choicesort[h]=tablica_choicesort[indeks_min];
		tablica_choicesort[indeks_min]=buf;
	}
	unsigned __int64 po_choicesort;
	po_choicesort=__rdtsc();
	FILE * choicesort;
	choicesort=fopen("choicesort.txt","w");
	if(choicesort==NULL)
	{
		printf("Blad pliku.");
		exit;
	}
	for(int i=0;i<99999;i++)
	{
		fprintf(choicesort,"%d\n",tablica_choicesort[i]);
	}
	fclose(choicesort);
	free(tablica_choicesort);
	return(po_choicesort-przed_choicesort);
}

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned __int64 czas_bubblesort,czas_insertsort,czas_choicesort; // tworzymy zmienne do przechowania ilosci cykli procesora wykorzystanych przez funkcje
	czas_bubblesort=BubbleSort(); // przypisujemy zmiennej wynik danej funkcji
	printf("Ilosc cykli wykonanych podczas funkcji BubbleSort : %I64d\n",czas_bubblesort); // wypisujemy otrzymany wynik
	czas_insertsort=InsertSort();
	printf("Ilosc cykli wykonanych podczas funkcji InsertSort : %I64d\n",czas_insertsort);
	czas_choicesort=ChoiceSort();
	printf("Ilosc cykli wykonanych podczas funkcji ChoiceSort : %I64d\n",czas_choicesort);
	if((czas_bubblesort < czas_insertsort) && (czas_bubblesort < czas_choicesort)) // jesli najlepszy okazal sie bubblesort, wypisujemy stosowny komunikat
	{
		printf("Najlepsza okazala sie funkcja BubbleSort! Wykonala tylko %I64d cykli.\n",czas_bubblesort);
		printf("Funkcja InsertSort zajela %I64d cykli wiecej, a ChoiceSort %I64d cykli wiecej.\n",czas_insertsort-czas_bubblesort,czas_choicesort-czas_bubblesort);
	}
	else if((czas_insertsort < czas_bubblesort) && (czas_insertsort < czas_choicesort)) // analogicznie dla insertsort
	{
		printf("Najlepsza okazala sie funkcja InsertSort! Wykonala tylko %I64d cykli.\n",czas_insertsort);
		printf("Funkcja BubbleSort zajela %I64d cykli wiecej, a ChoiceSort %I64d cykli wiecej.\n",czas_bubblesort-czas_insertsort,czas_choicesort-czas_insertsort);
	}
	else if((czas_choicesort < czas_bubblesort) && (czas_choicesort < czas_insertsort)) // i choicesort
	{
		printf("Najlepsza okazala sie funkcja ChoiceSort! Wykonala tylko %I64d cykli.\n",czas_choicesort);
		printf("Funkcja BubbleSort zajela %I64d cykli wiecej, a ChoiceSort %I64d cykli wiecej.\n",czas_bubblesort-czas_choicesort,czas_insertsort-czas_choicesort);
	}
	else printf("Programista nie przewidzial mozliwosci, ktora zaprezentowal program, wiec powiedz mu, ze jest idiota.");
	FILE * wyniki; // tworzymy zmienna plikowa, do ktorej zapisane zostana wyniki czasowe egzekucji kazdej z funkcji
	wyniki=fopen("wyniki.txt","w"); // tworzymy plik z wynikami
	fprintf(wyniki,"Cykle zuzyte przez funkcje BubbleSort : %I64d\n",czas_bubblesort); // zapisujemy wynik bubblesort'a
	fprintf(wyniki,"Cykle zuzyte przez funkcje InsertSort : %I64d\n",czas_insertsort); // insertsort'a
	fprintf(wyniki,"Cykle zuzyte przez funkcje ChoiceSort : %I64d",czas_choicesort); // choicesort'a
	fclose(wyniki); // i zamykamy plik
	getchar();
	return 0;
}