#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*); // функция сравнения для qsort()
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) // шесть проходов. для каждого выбираем M
{
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++)// в каждом proxod проходов
{
for(int k=0;k<M;k++) A[k]=rand(); // генерируем случайный массив размера M
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; // --||-- qsort
outs.precision (17);
//outs<<" Time("<<j+1<<") Massiv["<<M<<"] :\t"<<1000*TimeTempPod<<'\t'<<1000*TimeTempQsort<<endl;
//cout<<" Time("<<j+1<<") Massiv["<<M<<"] :\t"<<1000*TimeTempPod<<'\t'<<1000*TimeTempQsort<<endl;
}
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); // проверяем qsort
if(istina==false) cout<<" !!!FATAL ERROR!!!"<<endl; // если неверно
if(i==6) istina=false; // чтобы выйти из цикла do..while
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 = k>>1; // уменьшаем шаг сортировки
}
}
int Sravni(const void* x,const void* y) // x и 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) // аналогично проверяем быструю сортровку, но массив A
{
bool temp=true;
{
for (int i=0; i<N-1; i++)
if (A[i]>A[i+1]) temp=false;
}
return temp;
}
На си естественно
