#include<iostream>
#include<iomanip>
#include<conio.h>
#include<time.h>
#include<stdlib.h>
#include<fstream>
using namespace std;
int *A;
int *C;
void ShellSort(int);
bool ShellSortChec(int);
bool QwickSortChec(int);
int Sravni(const void*,const void*);
void main()
{
ofstream outs("Result.xls",ios::out);
srand((unsigned)time(NULL));
double StartTime, EndTime,Time,Time1,Time2,TimeTempPod,TimeTempQsort;
long N,M;
int i,j;
int proxod = 20;
bool istina;
system("CLS");
cout<<"\n VVEDI CHISLO ELEMENTOV MASSIVA\n N ( N>=10000 ) = ";
cin>>N;
while (N<10000)
{
cout<<"\n CHISLO \"N\" SLISHKOM MALENKOE!!!\n";
cout<<" N ( N>10000 ) = ";
cin>>N;
}
cout<<"------------------------------\n";
cout<<" IDET OBRABOTKA MASSIVA..."<<endl<<" ";
A=new int[N];
cout<<"------------------------------\n";
outs<<endl;
i=0;
outs<<"\tSortirovka Shell (msec)\tQsort (msec)"<<endl;
do
{
Time1=0;
Time2=0;
switch(i)
{
case 0:M=N; break;
case 1:M=N/2; break;
case 2:M=N/5; break;
case 3:M=N/10; break;
case 4:M=N/50; break;
case 5:M=N/100; break;
case 6:M=N/1000;break;
}
for(j=0;j<proxod;j++)
{
for(int k=0;k<M;k++) A[k]=rand();
StartTime = clock();
ShellSort(M);
EndTime = clock();
TimeTempPod = double(EndTime-StartTime)/CLOCKS_PER_SEC;
StartTime=clock();
qsort(A, M, sizeof(A[0]), Sravni);
EndTime=clock();
TimeTempQsort = double(EndTime-StartTime)/CLOCKS_PER_SEC;
Time1 = Time1 + TimeTempPod;
Time2 = Time2 + TimeTempQsort;
outs.precision (17);
}
cout<<" Srednee vremja sortirovki (in msec) dlja N = "<<setw(10)<<M<<"\t: " <<100*Time1/proxod<<'\t'<<100*Time2/proxod<<endl;
outs.precision (17);
outs<<M<<"\t " <<100*Time1/proxod<<'\t'<<100*Time2/proxod<<endl;
istina=QwickSortChec(M);
if(istina==false) cout<<" !!!FATAL ERROR!!!"<<endl;
if(i==6) istina=false;
i=i+1;
}
while (istina);
system("PAUSE");
system("CLS");
cout<<"------------------------------\n";
cout<<" SAVE FILE \"Result.xls\" \n";
system("PAUSE");
}
void ShellSort(int N)
{
C = new int[N];
copy(&A[0],&A[N-1],C);
int i,j,k;
int h;
k = N>>1;
while(k>0){
for (i=0;i<=(N-k);i++){
j = i;
while((j>=0)&&(C[j]>C[j+k])){
swap(C[j],C[j+k]);
j -= k;
}
}
k = k>>1;
}
}
int Sravni(const void* x,const void* y)
{
return ((*(int*)(x))-(*(int*)(y)));
}
bool ShellSortChec(int N)
{
bool temp=true;
for (int i=0; i<N-1; i++)
{
if (C[i]>C[i+1]) temp=false;
}
return temp;
}
bool QwickSortChec(int N)
{
bool temp=true;
{
for (int i=0; i<N-1; i++)
if (A[i]>A[i+1]) temp=false;
}
return temp;
}