Re: g_s?list_sort doesn't do stable sort

[Tim Janik <timj gtk org>]

On 8 Aug 2000, Kristian Hogsberg Kristensen wrote:

> 
> Hi,
> 
> The g_s?list_sort functions don't do a stable sort of the list
> elements, that is they don't preserve the order of elements considered
> equal by the comparison function.  The patch to fix this is really
> tiny (see below), so the decision to be made is wether to guarantee a
> stable sort or as in the case of libc's qsort explicitly state: "If
> two members compare as equal, their order in the sorted array is
> undefined." (from the glibc man page).
> 
> >From my point of view this is definately useful, and it doesn't change
> anything for people not expecting a stable sort.  I have a few places
> where I have to also consider the element index in the comparison
> function to get the desired behaviour.  On the other hand, leaving it
> unspecified allows you to change the implementation, but given that
> it's a linked list I dont see why you wouldn't use merge sort.
> 
> The patch also corrects some funky looking indentation, which somehow
> made it past the maintainers :-)

ok, i agree mith maciej here.
you had a typo in your patch though, so if you could
actually test it out and resubmit it against recent
CVS (cvs diff -u) that'd be good.
if i may be so bold, i wouldn't mind if you also cleaned up
the indentation and missing spaces in the surrounding
functions ;)


> 
> regards,
> Kristian

> Index: gslist.c
> ===================================================================
> RCS file: /cvs/gnome/glib/gslist.c,v
> retrieving revision 1.17
> diff -u -r1.17 gslist.c
> --- gslist.c	2000/07/26 11:01:59	1.17
> +++ gslist.c	2000/08/07 22:31:05
> @@ -591,18 +591,20 @@
>  
>    while (l1 && l2)
>      {
> -      if (compare_func(l1->data,l2->data) < 0)
> +      if (compare_func(l1->data,l2->data) <= 0)
>          {
> -	  l=l->next=l1;
> -	  l1=l1->next;
> +	  l->next = l1;
> +	  l = l->next

you mis a semicolon here.

> +	  l1 = l1->next;
>          } 

---
ciaoTJ