MAMEWorld >> EmuChat
Previous thread Previous  View all threads Index   Next thread Next   Flat Mode Flat  

krick
Get Fuzzy
Reged: 02/09/04
Posts: 4235
Send PM
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







Entire thread
Subject Posted by Posted on
* bug: chdman output depends on system qsort() implementation jmak 06/16/12 12:55 PM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/16/12 03:56 PM
. * Re: bug: chdman output depends on system qsort() implementation krick  06/16/12 04:16 PM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/16/12 05:50 PM
. * Re: bug: chdman output depends on system qsort() implementation krick  06/16/12 06:28 PM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/16/12 06:39 PM
. * Re: bug: chdman output depends on system qsort() implementation italieAdministrator  06/16/12 08:38 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/16/12 08:22 PM
. * Re: bug: chdman output depends on system qsort() implementation krick  06/17/12 07:38 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/17/12 07:44 PM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/17/12 10:13 PM
. * Re: bug: chdman output depends on system qsort() implementation AaronGiles  06/17/12 11:37 PM
. * Re: bug: chdman output depends on system qsort() implementation krick  06/18/12 04:08 AM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/16/12 10:13 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/17/12 06:47 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/17/12 06:58 PM
. * Re: bug: chdman output depends on system qsort() implementation R. Belmont  06/17/12 10:00 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/19/12 09:30 PM
. * Re: bug: chdman output depends on system qsort() implementation AaronGiles  06/17/12 02:09 AM
. * Re: bug: chdman output depends on system qsort() implementation TafoidAdministrator  06/16/12 09:06 PM
. * Re: bug: chdman output depends on system qsort() implementation krick  06/16/12 08:10 PM
. * Re: bug: chdman output depends on system qsort() implementation jmak  06/16/12 08:33 PM

Extra information Permissions
Moderator:  Robbbert, Tafoid 
0 registered and 352 anonymous users are browsing this forum.
You cannot start new topics
You cannot reply to topics
HTML is enabled
UBBCode is enabled
Thread views: 2169