Hi Peter, I have been looking at the heapsort algorithm that is implemented in nfstat.c and find it a bit "different" from the standard implementation. In nfstat.c (version 1.6b-snapshot) line 1379 (function heapSort) the heap is built as follows: --snip-- for (i = array_size - 1; i >= 0; i--) --snap-- Different sources on the internet (like http://electures.informatik.uni-freiburg.de/wiki/en/Implementierungen_von_HeapSort or http://en.wikipedia.org/wiki/Heapsort or http://www.algorithmist.com/index.php/Heap_sort.c) build the heap iterating until array_size/2 -1 as in: --snip-- for (i = (array_size / 2)- 1; i >= 0; i--) --snap-- At line 1395 (function heapSort) function Siftdown is called as: --snip-- siftDown(SortElement,i,0); --snap-- It should, probably, be --snip-- siftDown(SortElement,i-1,0); --snap-- to avoid replacing the just swapped max element in the heap. Further, in function Siftdown (lines 1400 through 1424) the child nodes are explored using 2* root_node +1 and 2* root_node +2 and the stop condition of the while seems somewhat different. Normally the child nodes correspond to root_node *2 and root_node *2 +1 Were these differences to the "standard" heapsort intentional? Are they some sort of optimization? Greetings, Luis
PS I just posted the same in the Discussion Forum, but realized that the
mailing list is probably more active. Sorry for double posting.
--
M.Sc. Luis Francisco Servin
Entwickler
PRESENSE Technologies GmbH
CarmentiS - Early Warning Expertise
http://www.carmentis.org
smime.p7s
Description: S/MIME cryptographic signature
------------------------------------------------------------------------------
_______________________________________________ Nfdump-discuss mailing list Nfdump-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/nfdump-discuss
