Juz ostatnie dzisiaj pytanko..
Mierze czasy 3 sortowań :my_heapsort, sort_heap, i qsort
Pod windowsem (Dev-C++) dostaje takie wyniki:
TEST DLA 500000 LICZB
my_heapsort: 1.65
std::sort_heap: 1.04
Qsort: 5.72
TEST DLA 1000000 LICZB
my_heapsort: 5.38
std::sort_heap: 3.9
Qsort: 63.99
TEST DLA 1500000 LICZB
my_heapsort: 15.04
std::sort_heap: 13.74
Qsort: nie wiem, bo sie nie kończy ;)
a na serwerze uczelni (SunOS) takie:
TEST DLA 500000 LICZB
my_heapsort: 4.87
std::sort_heap: 2.55
Qsort: 0.1
TEST DLA 1000000 LICZB
my_heapsort: 16.16
std::sort_heap: 11.28
Qsort: 0.32
TEST DLA 1500000 LICZB
my_heapsort: 33.85
std::sort_heap: 24.54
Qsort: 0.65
Skad takie rozbierzności? Które wyniki mogą byc poprawne?
Zamieszcze kod my_heap:
using namespace std;
template<class RandomAccessIterator, class P>
void my_heapsort(RandomAccessIterator First, RandomAccessIterator Last, P Comp)
{
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tmp;
int size=Last-First;
for (int i = size/2; i > 0; i--)
{
fix_heap(First, size,i, Comp);
}
while(size>=1)
{
tmp=*(First);
*(First)=*(Last);
*(Last)=tmp;
--Last;
--size;
fix_heap(First,size, 0, Comp);
}
}
template<class RandomAccessIterator, class P>
void fix_heap(RandomAccessIterator _first, unsigned int size, unsigned int node, P Comp)
{
int left = node*2;
int right = left+1;
int max = node;
if (size > left && Comp(*(_first+max), *(_first+left)))
max = left;
if ( right < size && Comp(*(_first+max),*(_first+right)) )
max = right;
if ( max != node ) {
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
value_type tmp;
tmp=*(_first+node);
*(_first+node)=*(_first+max);
*(_first+max)=tmp;
fix_heap(_first, size, max, Comp);
}
}
Jakby ktoś wiedzial jak to jeszcze przyspieszyć, bede ogromnie wdzięczny.