Witam. Mam pewien problem z programem, który piszę na zajęcia algorytmiki. Zadaniem jest posortować wektor składający się z kolejno od stu do miliona elementów za pomocą podanych algorytmów i policzyć czasy. I wszystko idzie dobrze. Z wyjątkiem Quick Sorta na wektorze zawierającym sto tysięcy elementów. Moja wykładowczyni powiedziała, że musi być to jakiś problem z pamięcią, ale nic więcej nie powiedziała. Pomocy?
Main:
#include "d.h"
#define napis ; {cout<<"LOSOWE LICZBY";}
#define wypisz10(liczby); {for (int i=0; i<10; i++) {cout << liczby[i]<<" ";}}
#define wypisz (wektor); {for (int i=0; i<10; i++) cout << wektor[i]<<" ";}
#define czas(start,stop){t=(double)(stop - start);}
using namespace std;
int main(int argc, char** argv)
{
srand((unsigned) time(0));
int ILE;
int r;
clock_t start;
clock_t stop;
vector <double> wektor;
cout <<endl<<endl<<"rodzaj danych\t |\trodzaj sortowania\t |\trozmiar danych\t |\tczas sortowania w klikach"<<endl;
for(int ile=10; ile<1000000; ile=ile*10)
{
r=ile-1;
for (int i=0; i<ile; i++)
{
wektor.push_back((double)rand() * 10/RAND_MAX);
}
start = clock();
MergeSort(wektor, 0, r);
stop = clock();
czas(start,stop);
cout <<"Wektor\t\t |\tMerge Sort\t\t |\t"<<ile<<"\t\t |\t"<<t<<endl;
wektor.clear();
for (int i=0; i<10; i++)
{
wektor.push_back((double)rand() * 10/RAND_MAX);
}
start = clock();
QuickSort(wektor, 0, r);
stop = clock();
czas(start,stop);
cout <<"Wektor\t\t |\tQuick Sort\t\t |\t"<<ile<<"\t\t |\t"<<t<<endl;
wektor.clear();
}
return 0;
}
.cpp:
#include "d.h"
using namespace std;
void MergeSort(vector <double> & A, int p, int r)
{
int q;
if (p<r)
{
q = (p+r)/2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
}
}
void Merge (vector <double> & A,int p, int q, int r)
{
int n1, n2, i, j, k;
n1 = q - p + 1;
n2 = r - q;
vector <double> L(n1+1);
vector <double> R(n2+1);
for (i=0; i<n1; i++) {L[i] = A[p+i];}
for (j=0; j<n2; j++) {R[j]=A[q+j+1];}
L[n1]=numeric_limits <double>::max();
R[n2]=numeric_limits <double>::max();
int a=0;
int b=0;
for( k=p; k<=r; k++)
{
if (L[a]<=R[b])
{
A[k]=L[a];
a++;
}
else
{
A[k]=R[b];
b++;
}
}
}
void QuickSort (vector <double> &A, int p, int r)
{
int q;
if (p<r)
{
q=Partition(A, p, r);
QuickSort (A, p, q-1);
QuickSort (A, q+1, r);
}
}
int Partition (vector <double> &A, int p, int r)
{
double x;
int i;
x=A[r];
i=p-1;
for(int j=p; j<=r-1; j++)
{
if (A[j] <= x)
{
i=i+1;
swap(A[i], A[j]);
}
}
swap (A[i+1], A[r]);
return i+1;
}
}