Re: [glob2-devel] okay to release!

[Bradley Arsenault]

On 4/4/07, Kai Antweiler <address@hidden> wrote:
> >> Please use std::stable_sort!
> >> std::sort might use random choices when two entries have the same key.
> >
> > Its the idea that counts, and std::sort doesn't use random choices,
>
> I don't know whether std::sort uses random choices now.
> It uses introsort which is based on quicksort.
> But even if it is not random now, it might be in the future.

std::sort is implementation defined. gcc uses a sort of combination
based sort, introsort on low numbers of elements (which is pretty much
anything glob2 would use) and different sorts, like merge sort or
quick sort, on higher numbers of elements.

> Random choices are common in sorting algorithms.
> e.g: a simple quicksort implementation without random choices
> performs very poor some data.
> Choosing the pivot elements randomly guarantees mostly good
> performance for every input.

Some sorting algorithms. In a direct comparison when two elements are
the same, I doubt a single algorithm will use a random choice. I have
never heard of this, its just unnecceccarry overhead when just leaving
them in current order doesn't affect how sorted the list becomes, and
will be faster than taking the time to generate a random binary number
and move the elements if nesseccarry.

> > its merely that it is unpredictable. Certain algorithms will move
> > elements in a manner that makes them unstable, where as others will
> > compare like keys and maintain relative order.
>
> Sometimes, yes.  But sometimes randomness is used.
> Take std::stable_sort and you're on the safe side.
>
> --
> Kai Antweiler
>
>
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel


--
Really. I'm not lieing. Bradley Arsenault.