Проблема с таймером

  • Автор темы SunnyXD
  • Дата начала
S

SunnyXD

#1
Здравствуйте! Нам тут задали задачку на программировании. Все реализовала а вот с таймером проблема получается.

Задача: реализовать алгоритм быстрой сортировки рекурсивным способом. при этом последовательность чисел взять из файла и измерить время выполнения сортировки.
В программе из файла считывается в массив неупорядоченная последовательность 4000 чисел, а затем упорядочивается. Я запускаю таймер перед началом выполнения упорядочивания и останавливаю после завершения упорядочивания, а результат выводится 0...(
может я что то не так делаю?почему время работы функции упорядочивания=0? я просто новичок в С++. Вот полный листинг программы
Код:
#include <clx.h>
#pragma hdrstop
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <windows.h>
#pragma argsused
using namespace std;

template<class T>
void quickSortR(T* a, long N) {
long i = 0, j = N;
T temp, p;
p = a[ N>>1 ];
do
{
while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j)
{
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
}
while ( i<=j );
if ( j > 0 ) quickSortR(a, j);
if ( N > i ) quickSortR(a+i, N-i);
}


int main()
{
char ch[65], c;
int count;
ifstream in;
in.open("number.txt");
int A[4000];
int i=0;
in.getline(ch, sizeof(ch));
while (!in.eof())
{
A[i]=atoi(ch);
in.getline(ch, sizeof(ch));
i++;
count=i;

}
in.close();
int e=count-1;
int start=GetTickCount();		//запуск таймера
quickSortR(A,e);			 //сортировка массива из 4000 чисел
int end=GetTickCount();			 //остановка таймера
int res=end-start;				 //вычисление временного интервала выполнения сортировки
for (int i=0; i<count; i++) {cout<<A[i]<<"; ";}
cout<<" "<<endl<<"Work time="<<res;	//вывод временного интервала (собственно он и равен 0)
cin>>c;
}
 
A

alexsid

#2
4000 это очень мало
для точности используй 10-100 повторений и выводи потом среднее значение
 
M

Maxx

#3
точность GetTickCount где-то 10-15 мс
для точных вычислений временнЫх параметров можно использовать функции QueryPerformanceCounter и QueryPerformanceFrequency
и как говорил alexsid:
4000 это очень мало
почти все алгоритмы сортировки при таком количестве данных будут показывать практически одинаковые результаты по времени
 
J

JORIK

#4
Вообще QuickSort - является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена.Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива.Улучшение самого неэффективного прямого метода сортировки дало в результате самый эффективный улучшенный метод.
Когда мы делали похожую работу,то мы брали размерность массива от 100000 до 1 миллиона элементов.Могу даже показать график зависимости времени о количества элементов массива.
В приведенных ниже графиках у - время (мс), а х - размерность массива. R на графике - случайно сгенерированный массив, S – отсортированный массив, A – массив, отсортированный по убыванию.

в коде примерно это так:

int M;
long long N,i;
printf("Enter M: ");
scanf("%d",&M);
N=(long long)pow(2.0,(double)M);
int *arr=(int*)malloc(N*sizeof(int));
for(i=0;i<N;i++)
arr=rand()%10;
putchar('\n');
 
A

allsolovey

#5
Почему в Borland C 3.1 не работает GetTickCount().Компилируется а вот при запуске ошибка Undefined symbol GETTICKCOUNT in module ..cpp.Windows.h подключен.