// Insertion Sort.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "math.h"
#include "string"
#include "iostream"
#include "fstream"
#include "cstdlib"
using namespace std;
class ALG
{
protected:
int rozmiar;
int * data;
int counter;
int * wyniki;
typedef void (ALG::* wskMetoda)();
wskMetoda Akcja;
private:
char const * mode;
public:
//q: ALG nie potrzebuje domyslnego nic nierobiacego konstruktora
ALG(int size, int c) :
rozmiar(size), //q: jesli chcesz miec
data(new int[rozmiar+1]), //q: ladny, c++owy program
counter(c), //q: to co mozesz, inicjalizuj za pomoca
wyniki(new int[counter+1]) //q: listy inicjalizacyjnej
{
data[rozmiar] = INT_MAX;
srand(time(0));
}
~ALG() //q: swiat bedzie Ci wdzieczny, jak bedziesz po sobie sprzatac wlasne smieci
{
delete[] wyniki; wyniki=0;
delete[] data; data=0;
}
private:
void printData()
{
printf("\n\nTablica typu: %s [%d]\n", mode, rozmiar);
for(int a = 0; a<rozmiar; a++)
printf("[%d] => %d\n", a, data[a]);
}
float srednia()
{
float wynik=0.0;
for(int a=0; a<rozmiar; a++) wynik+=wyniki[a]; // q: zastanow sie nad tym, co jest rozmiarem tablicy 'wyniki'
return wynik/counter;
}
float odchylenie()
{
float odchylenie=0.0;
float roznica=0.0;
for (int i=0; i < rozmiar; i++)
{
roznica = wyniki[i] - srednia(); // q: zastanow sie nad tym, co jest rozmiarem tablicy 'wyniki'
odchylenie += pow(roznica, 2);
}
odchylenie /= rozmiar;
return sqrt(odchylenie) / (counter-1); // q: sprawdz czy faktycznie -1 przy counter
}
public:
// q: metoda virtual przeznaczona do wypelnienia przez klasy-dzieci moze byc pure virtual
// q: i w ogole nie miec wlasnego ciala.
// q: po co? sprobuj teraz napisac klase-dziecko ktore nie ma wlasnej metody run!
virtual void run() = 0;
void setAkcja(wskMetoda akcja) { Akcja = akcja; }
void generateRandomData()
{
mode = "Random";
for(int a = 0; a<rozmiar; a++)
data[a] = (rand()/**rand()*/) % 111; //q: skoro modulo 111, to po co rand()*rand()? RAND_MAX jest >> 111
}
void getFromUser()
{
mode = "User";
system("cls");
for(int a = 0; a<rozmiar; a++)
{
printf("Podaj element [%d] => ",a);
scanf("%d", &data[a]); //q: nie sprawdzasz czy scanf zwrocil '1' - tzn. czy wpisano poprawne dane
}
}
void getFile()
{
mode = "Z pliku";
ifstream odczyt = ifstream("tablica.txt");
while (!odczyt.good())
{
printf("blad w odczytywaniu pliku\n");
exit(0);
}
// odczyt >> skipws; // q: o ile dobrze pamietam, to juz jest defaultowo na strumieniu
int a, b = 0;
while (odczyt.good())
{
odczyt >> a; // q: jezeli 'ostatni' odczyt sie nie powiedzie, linia ponizej wstawi smieci do tablicy
data[b++] = a; // q: a co jezeli liczb jest wiecej niz rozmiar data[]? tzn. gdy b > rozmiar ?
}
// q: a co jesli liczb w pliku bylo mniej niz rozmiar?
odczyt.close();
}
void printResults()
{
printf("\npowtorzen: %d", counter);
printf("\nsrednia: %f", srednia());
printf("\nodchylenie: %f", odchylenie());
printf("\n\n");
}
};
class P : public ALG
{
public:
// q: tak powinien wygladac konstruktor klasy dziedziczacej
// q: listy inicjalizacyjne sa fajne, gdyz pozwalaja Ci skorzystac z
// q: argumentowego konstruktora bazowego
P(int size, int c) : ALG(size, c) { } //q: te klamry musza tutaj byc, nawet jesli w nich w srodku nic nie ma. metoda musi miec cialo, albo byc pure virtual
void run()
{
for(int a=0; a<counter; a++)
{
(this->*Akcja)();
wyniki[a]=partition(0, rozmiar-2); // q: sprawdz czy faktycznie -2 przy rozmiar
}
printResults();
}
int partition(int lewa, int prawa) // q: przyznam, nie chcialo mi sie sprawdzac
{
int value = data[0];
int i = lewa;
int j = prawa + 1;
int temp;
do
{
do i++; while (data[i] <= value);
do j--; while (data[j] >= value && j>0);
if (i <= j)
{
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
} while (j >= i);
data[lewa] = data[j];
data[j] = value;
return j;
}
};
class IS : public ALG
{
public:
// q: tak powinien wygladac konstruktor klasy dziedziczacej
// q: listy inicjalizacyjne sa fajne, gdyz pozwalaja Ci skorzystac z
// q: argumentowego konstruktora bazowego
IS(int size, int c) : ALG(size, c) { }
int sort() // q: przyznam, nie chcialo mi sie sprawdzac
{
int liczba,a,b, podstawienia;
podstawienia = 0;
for(a=1; a<rozmiar; a++) // zaczynamy porównywanie od elementu 2 w tablicy
{
liczba = data[a]; // zapamiętujemy element
b=a-1; // ustawiamy sobie poprzedni element
while(data[b]>liczba && b>=0) // dopóki element poprzedni jest większy od następnego
{
data[b+1]=data[b]; // przesuwamy poprzedni w dół
podstawienia++;
b--;
}
data[b+1] = liczba; // wstawiamy zapamiętany element
}
return podstawienia; // zwraca ilosc podstawien
}
void run()
{
for(int a=0; a<counter; a++)
{
(this->*Akcja)();
wyniki[a]=sort();
}
printResults();
}
};
int main(int argc, char* argv[])
{
do
{
int wybor;
system("cls");
printf("## Sortowanie tablic ##\n"
"## Grzegorz Kaszuba ##\n\n"
"Wybierz algorytm:\n"
" 1\\ Insertion Sort\n"
" 2\\ Partition\n\nwybor: ");
scanf("%d",&wybor);
ALG * sortowacz = 0;
//q: skoro juz operujesz na ALG* to po co tworzyc w ciemno obiekty i potem brac ptr na nie?
switch(wybor)
{
case 1: sortowacz = new IS(10, 100); break; //q: po prostu stworz sobie dany obiekt dynamicznie
case 2: sortowacz = new P (10, 100); break; //q: w momencie w ktorym wiesz ze akurat on bedzie Ci dalej potrzebny
default: printf("Podano niewlasciwy algorytm sortowania!\n"); return 0;
}
// q: btw. jestes pewien ze chcesz miec size=10 oraz counter=100?
// q: jesli tak, powodzenia przy petlach for(int a=0; a<counter; a++) akcja() gdy akcja = pobierzodusera
printf("\nWybierz typ danych:\n"
" 1\\ wprowadz dane recznie\n"
" 2\\ losowe dane\n"
//q: ciach
" 4\\ dane z pliku tablica.txt\n\n"
"wybor: ");
scanf("%d",wybor);
switch(wybor)
{
case 1: sortowacz->setAkcja( &ALG::getFromUser ); break;
case 2: sortowacz->setAkcja( &ALG::generateRandomData ); break;
//q: ciach
case 4: sortowacz->setAkcja( &ALG::getFile ); break;
default: sortowacz->setAkcja( &ALG::getFromUser ); break;
}
sortowacz->run();
system("pause");
delete sortowacz; sortowacz=0; //q: warto by bylo po sobie jeszcze posprzatac te dynamiczne obiekty
} while (1==1);
return 0;
}
To Ci sie skompiluje i wyglada jakby moglo dzialac poprawnie. Nie sprawdzalem czy dziala poprawnie, wiec pewnie tak nie jest, jednak fragmenty ktore zmienilem sa prawieze na pewno poprawne i jesli nie dzialaja - zaloz ze nie dzialaja przez bledy pozostawione w innych miejscach Tobie do przemyslenia. Nie bede opisywal co zmienilem, gdyz to bez sensu, uzyj Diff'a jesli masz problemy ze znalezieniem roznic. Popozostawialem Ci mase komentarzy gdzie mozeszmiec/pewniemasz jakies wpadki jeszcze. To na pewno nie sa wszystkie. Czesci kodu nie chcialo mi sie ogladac, a te ktore akurat obejrzalem - nie analizowalem zbyt doglebnie.