#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 pamiecNa pewno nie jest to najlepszy program z tych przyslanych do Pana, pewnie nie jest nawet dobry - w koncu jest proporcjonalnydo moich umiejetnosci, ale jestem z niego dumny, bo zajal mi niemalo czasu i dziala jak nalezy. ;)-D.K. */// std::swap jest beznadziejneunsigned __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;}