|
Re: bug: chdman output depends on system qsort() implementation
06/16/12 04:16 PM
|
|
|
http://lmgtfy.com/?q=Quicksort+is+not+a+stable+sort
Code:
/src/lib/util/huffman.c
529 //------------------------------------------------- 530 // tree_node_compare - compare two tree nodes 531 // by weight 532 //------------------------------------------------- 533 534 int CLIB_DECL huffman_context_base::tree_node_compare(const void *item1, const void *item2) 535 { 536 const node_t *node1 = *(const node_t **)item1; 537 const node_t *node2 = *(const node_t **)item2; 538 return node2->m_weight - node1->m_weight; 539 }
...
565 // sort the list by weight, largest weight first 566 qsort(list, listitems, sizeof(list[0]), tree_node_compare);
http://www.gnu.org/software/libc/manual/html_node/Array-Sort-Function.html
Quote:
Warning: If two objects compare as equal, their order after sorting is unpredictable. That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects.
If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary.
I think the bottom line is that either...
1) the qsort comparison function would need to be modified to handle the case when items are equal and sort them by another key (address?) that guarantees stable results
...or...
2) a different "stable" sort needs to be used. i.e. mergesort.
Here's a real-world example of modifying the comparison function...
http://old.nabble.com/RFA:-GCC-4.2.1:-Stabalizing-coalesce_list%27s-qsort-td12233553.html
GroovyMAME support forum on BYOAC
|
|