Witam,
Mój problem polega na tym, że program się sypie, gdy próbuję wykonać pomiary.
Wydaje mi się, że chodzi o alokacje/zwolnienie pamięci, ale nie mogę nic wykombinować i proszę o pomoc.
Tylko 1 opcja w menu działa bez zarzutu... no i 7.
Oto kod:
#include <cstdlib>
#include <time.h>
#include <iostream>
using namespace std;
void insertion(int *tablica, int rozmiar)
{
int i, j, temp;
for (i=1; i<rozmiar; i++)
{
temp=tablica[i];
j=i;
while (j>0 && tablica[j-1]>temp)
{
tablica[j]=tablica[--j];
}
tablica[j]=temp;
}
}
void selection(int *tablica, int rozmiar)
{
int i, j, index, temp;
for (i=0; i<rozmiar-1; i++)
{
index=i;
for (j=i+1; j<rozmiar; j++)
if (tablica[j]<tablica[index])
index=j;
if (index!=i)
{
temp=tablica[i];
tablica[i]=tablica[index];
tablica[index]=temp;
}
}
}
void heapify(int *tablica, int x, int rozmiar)
{
int lewy=2*x+1, prawy=lewy+1, max=x;
if (lewy<=rozmiar && tablica[lewy]>tablica[max])
max=lewy;
if (prawy<=rozmiar && tablica[prawy]>tablica[max])
max=prawy;
if (max!=x)
{
int temp=tablica[x];
tablica[x]=tablica[max];
tablica[max]=temp;
heapify(tablica,max,rozmiar);
}
}
void heap(int *tablica, int rozmiar)
{
int i, temp;
rozmiar--;
for (i=rozmiar/2; i>=0; i--)
heapify(tablica,i,rozmiar);
for (i=rozmiar; i>0; i--)
{
temp=tablica[0];
tablica[0]=tablica[i];
tablica[i]=temp;
heapify(tablica,0,i-1);
}
}
void quicksort(int *tablica, int x, int y)
{
int i=x, j=y, mediana=tablica[(x+y)/2], temp;
while (j>=i)
{
while (tablica[i] < mediana)
i++;
while (tablica[j] > mediana)
j--;
if (i<=j)
{
temp=tablica[i];
tablica[i++]=tablica[j];
tablica[j--]=temp;
}
}
if (x<j)
quicksort(tablica,x,j);
if (i<y)
quicksort(tablica,i,y);
}
void ciag_l(int *tablica, int rozmiar)
{
int i;
for (i = 0; i < rozmiar; ++i)
{
tablica[i] = rand() % rozmiar;
}
}
void ciag_r(int *tablica, int rozmiar)
{
int i;
tablica[0] = 1;
for (i = 1; i < rozmiar; ++i)
{
tablica[i] = tablica[i-1] + 1;
}
}
void ciag_m(int *tablica, int rozmiar)
{
int i;
tablica[0] = rozmiar;
for (i = 1; i < rozmiar; ++i)
{
tablica[i] = tablica[i-1]-1;
}
}
void ciag_s(int *tablica, int rozmiar)
{
int i;
for (i = 0; i < rozmiar; ++i)
{
tablica [i] = 1;
}
}
void ciag_v(int *tablica, int rozmiar)
{
int przyrost = rozmiar/2;
int licznik = 1;
int i, x = 1;
tablica[przyrost] = 1;
while(licznik < rozmiar)
{
if(przyrost - x >= 0)
tablica[przyrost - x] = ++licznik;
if(przyrost + x < rozmiar)
tablica[przyrost + x++] = ++licznik;
}
}
int main(int argc, char *argv[])
{
int menu, i, rozmiar, *tablica;
int elementy[27]={10,100,1000,2500,5000,6000,7000,8000,9000,
10000,12500,25000,37500,50000,62500,75000,87500,100000,150000,
200000,400000,800000,1000000,2000000,4000000,8000000,10000000};
int y;
float czas1 = 0, czas2 = 0, czas3 = 0, czas4 = 0;
time_t t;
srand((unsigned) time(&t));
bool over1 = false, over2 = false, over3 = false, over4 = false;
//tablica = new int[rozmiar];
do
{
do
{
cout << "WYBIERZ OPCJE: " << endl
<< "1 - Prezentacja sortowan" << endl
<< "2 - Test 1 - ciagi losowe" << endl
<< "3 - Test 2 - ciagi rosnace" << endl
<< "4 - Test 3 - ciagi malejace" << endl
<< "5 - Test 4 - ciagi stale" << endl
<< "6 - Test 5 - ciagi v-ksztaltne" << endl
<< "7 - Zakoncz program" << endl;
cin >> menu;
}
while(menu == 0 || menu > 7);
switch(menu)
{
case 1:
{
cout << "------------------ PREZENTACJA SORTOWAN -----------------"
<< endl << endl;
tablica = new int[rozmiar];
rozmiar = 20;
cout << "INSERTION SORT: " << endl << endl;
ciag_l(tablica, rozmiar);
cout << "Ciag losowy:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
insertion(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_r(tablica, rozmiar);
cout << "Ciag rosnacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
insertion(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_m(tablica, rozmiar);
cout << "Ciag malejacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
insertion(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_s(tablica, rozmiar);
cout << "Ciag staly:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
insertion(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_v(tablica, rozmiar);
cout << "Ciag v-ksztaltny:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
insertion(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl << endl;
//------------------------------------------------------------------------------
cout << "SELECTION SORT: " << endl << endl;
ciag_l(tablica, rozmiar);
cout << "Ciag losowy:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
selection(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_r(tablica, rozmiar);
cout << "Ciag rosnacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
selection(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_m(tablica, rozmiar);
cout << "Ciag malejacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
selection(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_s(tablica, rozmiar);
cout << "Ciag staly:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
selection(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_v(tablica, rozmiar);
cout << "Ciag v-ksztaltny:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
selection(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl << endl;
//------------------------------------------------------------------------------
cout << "HEAP SORT: " << endl << endl;
ciag_l(tablica, rozmiar);
cout << "Ciag losowy:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
heap(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_r(tablica, rozmiar);
cout << "Ciag rosnacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
heap(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_m(tablica, rozmiar);
cout << "Ciag malejacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
heap(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_s(tablica, rozmiar);
cout << "Ciag staly:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
heap(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_v(tablica, rozmiar);
cout << "Ciag v-ksztaltny:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
heap(tablica, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl << endl;
//------------------------------------------------------------------------------
cout << "QUICK SORT: " << endl << endl;
ciag_l(tablica, rozmiar);
cout << "Ciag losowy:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
quicksort(tablica, 0, rozmiar-1);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_r(tablica, rozmiar);
cout << "Ciag rosnacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
quicksort(tablica, 0, rozmiar-1);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_m(tablica, rozmiar);
cout << "Ciag malejacy:" << endl;
cout << tablica[0] << " ";
for (i = 1; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
quicksort(tablica, 0, rozmiar-1);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_s(tablica, rozmiar);
cout << "Ciag staly:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
quicksort(tablica, 0, rozmiar);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
ciag_v(tablica, rozmiar);
cout << "Ciag v-ksztaltny:" << endl;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl;
quicksort(tablica, 0, rozmiar-1);
cout << "Posortowany:" << endl;;
for (i = 0; i < rozmiar; ++i)
{
cout << tablica[i] << " ";
}
cout << endl << endl;
}
break;
case 2:
{
cout << "Test 1 - CIAGI LOSOWE:" << endl;
for(i=0; i<27; i++)
{
//tablica = new int[rozmiar];
rozmiar = elementy[i];
tablica = new int[rozmiar];
if(czas1 >= 15)
{
over1 = true;
czas1 = 0;
}
if(over1 == false)
{
ciag_l(tablica, rozmiar);
czas1=clock();
insertion(tablica, rozmiar);
czas1=clock()-czas1;
czas1/=CLOCKS_PER_SEC;
}
cout << "IS: " << czas1 << "s || ";
if(czas2 >= 15)
{
over2 = true;
czas2 = 0;
}
if(over2 == false)
{
ciag_l(tablica, rozmiar);
czas2=clock();
selection(tablica, rozmiar);
czas2=clock()-czas2;
czas2/=CLOCKS_PER_SEC;
}
cout << "SS: " << czas2 << "s || ";
if(czas3 >= 15)
{
over3 = true;
czas3 = 0;
}
if(over3 == false)
{
ciag_l(tablica, rozmiar);
czas3=clock();
heap(tablica, rozmiar);
czas3=clock()-czas3;
czas3/=CLOCKS_PER_SEC;
}
cout << "HS: " << czas3 << "s || ";
if(czas4 >= 15)
{
over4 = true;
czas4 = 0;
}
if(over4 == false)
{
ciag_l(tablica, rozmiar);
czas4=clock();
quicksort(tablica, 0, rozmiar-1);
czas4=clock()-czas4;
czas4/=CLOCKS_PER_SEC;
}
cout << "QS: " << czas4 << "s || ";
cout << "n = " << rozmiar << endl;
}
cout << endl;
}
break;
case 3:
{
cout << "Test 1 - CIAGI ROSNACE:" << endl;
for(i=0; i<27; i++)
{
//tablica = new int[rozmiar];
rozmiar = elementy[i];
tablica = new int[rozmiar];
if(czas1 >= 15)
{
over1 = true;
czas1 = 0;
}
if(over1 == false)
{
ciag_r(tablica, rozmiar);
czas1=clock();
insertion(tablica, rozmiar);
czas1=clock()-czas1;
czas1/=CLOCKS_PER_SEC;
}
cout << "IS: " << czas1 << "s || ";
if(czas2 >= 15)
{
over2 = true;
czas2 = 0;
}
if(over2 == false)
{
ciag_r(tablica, rozmiar);
czas2=clock();
selection(tablica, rozmiar);
czas2=clock()-czas2;
czas2/=CLOCKS_PER_SEC;
}
cout << "SS: " << czas2 << "s || ";
if(czas3 >= 15)
{
over3 = true;
czas3 = 0;
}
if(over3 == false)
{
ciag_r(tablica, rozmiar);
czas3=clock();
heap(tablica, rozmiar);
czas3=clock()-czas3;
czas3/=CLOCKS_PER_SEC;
}
cout << "HS: " << czas3 << "s || ";
if(czas4 >= 15)
{
over4 = true;
czas4 = 0;
}
if(over4 == false)
{
ciag_r(tablica, rozmiar);
czas4=clock();
quicksort(tablica, 0, rozmiar-1);
czas4=clock()-czas4;
czas4/=CLOCKS_PER_SEC;
}
cout << "QS: " << czas4 << "s || ";
cout << "n = " << rozmiar << endl;
}
cout << endl;
}
break;
case 4:
{
cout << "Test 1 - CIAGI MALEJACE:" << endl;
for(i=0; i<27; i++)
{
rozmiar = elementy[i];
tablica = new int[rozmiar];
if(czas1 >= 15)
{
over1 = true;
czas1 = 0;
}
if(over1 == false)
{
ciag_m(tablica, rozmiar);
czas1=clock();
insertion(tablica, rozmiar);
czas1=clock()-czas1;
czas1/=CLOCKS_PER_SEC;
}
cout << "IS: " << czas1 << "s || ";
if(czas2 >= 15)
{
over2 = true;
czas2 = 0;
}
if(over2 == false)
{
ciag_m(tablica, rozmiar);
czas2=clock();
selection(tablica, rozmiar);
czas2=clock()-czas2;
czas2/=CLOCKS_PER_SEC;
}
cout << "SS: " << czas2 << "s || ";
if(czas3 >= 15)
{
over3 = true;
czas3 = 0;
}
if(over3 == false)
{
ciag_m(tablica, rozmiar);
czas3=clock();
heap(tablica, rozmiar);
czas3=clock()-czas3;
czas3/=CLOCKS_PER_SEC;
}
cout << "HS: " << czas3 << "s || ";
if(czas4 >= 15)
{
over4 = true;
czas4 = 0;
}
if(over4 == false)
{
ciag_m(tablica, rozmiar);
czas4=clock();
quicksort(tablica, 0, rozmiar-1);
czas4=clock()-czas4;
czas4/=CLOCKS_PER_SEC;
}
cout << "QS: " << czas4 << "s || ";
cout << "n = " << rozmiar << endl;
}
cout << endl;
}
break;
case 5:
{
cout << "Test 1 - CIAGI STALE:" << endl;
for(i=0; i<27; i++)
{
rozmiar = elementy[i];
tablica = new int[rozmiar];
if(czas1 >= 15)
{
over1 = true;
czas1 = 0;
}
if(over1 == false)
{
ciag_s(tablica, rozmiar);
czas1=clock();
insertion(tablica, rozmiar);
czas1=clock()-czas1;
czas1/=CLOCKS_PER_SEC;
}
cout << "IS: " << czas1 << "s || ";
if(czas2 >= 15)
{
over2 = true;
czas2 = 0;
}
if(over2 == false)
{
ciag_s(tablica, rozmiar);
czas2=clock();
selection(tablica, rozmiar);
czas2=clock()-czas2;
czas2/=CLOCKS_PER_SEC;
}
cout << "SS: " << czas2 << "s || ";
if(czas3 >= 15)
{
over3 = true;
czas3 = 0;
}
if(over3 == false)
{
ciag_s(tablica, rozmiar);
czas3=clock();
heap(tablica, rozmiar);
czas3=clock()-czas3;
czas3/=CLOCKS_PER_SEC;
}
cout << "HS: " << czas3 << "s || ";
if(czas4 >= 15)
{
over4 = true;
czas4 = 0;
}
if(over4 == false)
{
ciag_s(tablica, rozmiar);
czas4=clock();
quicksort(tablica, 0, rozmiar-1);
czas4=clock()-czas4;
czas4/=CLOCKS_PER_SEC;
}
cout << "QS: " << czas4 << "s || ";
cout << "n = " << rozmiar << endl;
}
cout << endl;
}
break;
case 6:
{
cout << "Test 1 - CIAGI V-KSZTALTNE:" << endl;
for(i=0; i<27; i++)
{
rozmiar = elementy[i];
tablica = new int[rozmiar];
if(czas1 >= 15)
{
over1 = true;
czas1 = 0;
}
if(over1 == false)
{
ciag_v(tablica, rozmiar);
czas1=clock();
insertion(tablica, rozmiar);
czas1=clock()-czas1;
czas1/=CLOCKS_PER_SEC;
}
cout << "IS: " << czas1 << "s || ";
if(czas2 >= 15)
{
over2 = true;
czas2 = 0;
}
if(over2 == false)
{
ciag_v(tablica, rozmiar);
czas2=clock();
selection(tablica, rozmiar);
czas2=clock()-czas2;
czas2/=CLOCKS_PER_SEC;
}
cout << "SS: " << czas2 << "s || ";
if(czas3 >= 15)
{
over3 = true;
czas3 = 0;
}
if(over3 == false)
{
ciag_v(tablica, rozmiar);
czas3=clock();
heap(tablica, rozmiar);
czas3=clock()-czas3;
czas3/=CLOCKS_PER_SEC;
}
cout << "HS: " << czas3 << "s || ";
if(czas4 >= 15)
{
over4 = true;
czas4 = 0;
}
if(over4 == false)
{
ciag_v(tablica, rozmiar);
czas4=clock();
quicksort(tablica, 0, rozmiar-1);
czas4=clock()-czas4;
czas4/=CLOCKS_PER_SEC;
}
cout << "QS: " << czas4 << "s || ";
cout << "n = " << rozmiar << endl;
}
cout << endl;
}
break;
case 7:
{
delete[] tablica;
return EXIT_SUCCESS;
}
break;
}
}
while(menu != 7);
system("PAUSE");
return EXIT_SUCCESS;
}