[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [glob2-devel] okay to release!
From: |
Kai Antweiler |
Subject: |
Re: [glob2-devel] okay to release! |
Date: |
Wed, 04 Apr 2007 22:11:21 +0200 |
User-agent: |
Gnus/5.1007 (Gnus v5.10.7) XEmacs/21.4.20 (linux) |
>> 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.
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.
> 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
- Re: [glob2-devel] okay to release!, (continued)
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/03
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/03
- Re: [glob2-devel] okay to release!, Robert Martin, 2007/04/03
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/03
- Re: [glob2-devel] okay to release!, Robert Martin, 2007/04/03
- Re: [glob2-devel] okay to release!, Kyle Lutze, 2007/04/04
- Re: [glob2-devel] okay to release!, donkyhotay, 2007/04/04
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/03
- Re: [glob2-devel] okay to release!, Kai Antweiler, 2007/04/04
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/04
- Re: [glob2-devel] okay to release!,
Kai Antweiler <=
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/04
- Re: [glob2-devel] okay to release!, Stéphane Magnenat, 2007/04/05
- Re: [glob2-devel] okay to release!, Kai Antweiler, 2007/04/05
- Re: [glob2-devel] okay to release!, Bradley Arsenault, 2007/04/05
Re: [glob2-devel] okay to release!, Kai Antweiler, 2007/04/04