🚀 go-pugleaf

"Jean-Marc Bourguet" <jm@bourguet.org> wrote in message
news:pxbslwa21yn.fsf@news.bourguet.org...
> "Charlie Gordon" <news@chqrlie.org> writes:
>
> > > Ca ressemble � un bubble sort, c'est un excellent algo de tri pour les
> > > listes qui font 1 ou 2 �l�ments.

Mauvaise attribution, c'est Harpo qui a dit cela.

> En pratique le bubble sort (ou le shaker sort qui est une variante)
> est bien adapte aux cas ou les donnees sont quasiment triees: il peut
> avoir un comportement en n sous certaines conditions alors qu'un quick
> sort -- mal implemente -- peut meme exhiber un comportement
> quadratique .  Un bon professionnel -- puisque le terme a ete lance --
> va donc l'utiliser dans certains cas.
>
> > Non, c'est effectivement un tri par insertion (complexit� n^2),
> > nettement plus efficace que bubble sort (n^3 ?),
>
> bubble sort est aussi du n^2 (facile a montrer: a chaque passe au
> moins un element en plus est a sa place terminale)

Mais � un prix pplus important que le tri par insertion : plus d'�changes.

> > mais moins que qsort (n.log(n)),
>
> qsort c'est difficile a dire, il n'y a pas de contrainte.
> L'implementation classique est un quick sort qui a une complexite
> quadratique egalement dans le pire cas (attention, suivant la maniere
> de choisir le pivot, et les caracteristiques des donnees, le pire cas
> peut arriver de maniere certaine dans des cas courants) mais n log n
> en moyenne.  J'ai deja vu decrite des implementations recourant au
> heap sort (garanti n log n -- mais avec une constante relativement
> mauvaise) si elles remarquent que la recursion a l'air de prendre un
> mauvais bout.

Oui, la complexit� de quick sort est un sujet difficile, et son impl�mentation
est une source de maux de tete consid�rable.
On peut ajouter au rang de ses "probl�mes" la non stabilit� du tri et la
propension � produire des r�sultats surprenants quand la fonction de comparaison
a de mauvaises proprietes : pas exemple strcasecmp n'est pas n�cessairement
transitive.

-- 
Chqrlie.