Задача: Сортировка методом шелла

  • Автор темы zlosend
  • Дата начала
Z

zlosend

#1
Разработать программу для расчета времени, необходимого для выполнения сортировки методом Шелла, массив данных должен быть считан из файла, указанного пользователем, и отображен в диалоге до и после сортировки.
Кто может помочь в icq 364288 ;) На си естественно

Добавлено: Если будет антиспам, тогда вконтакт zlosend.vkontakte.ru <_<
Пи.эс:язык С++ естественно
 

DarkKnight

Well-known member
01.08.2010
653
0
#3
2 zlosend : Если не надумал еще ни у кого заказывать, помогу, но при условии что сам хотя бы что-то напишишь....
 
Z

zlosend

#4
C++:
#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;
}
Примерно так придумал. С прикручиванием интерфейся огромные проблемы...
 

DarkKnight

Well-known member
01.08.2010
653
0
#5
Закинь еще входной файл данных...
И какой именно интерфейс должен быть?