Archives pour la catégorie Tri

Le Multirator

Lors du dernier concours du meilleur « Meilleur Développeur de France », dont on vous pouvez retrouver un résumé ici, une des épreuves consistait à programmer un Multirator. Ce terme est une invention personnelle pour désigner un Iterator piochant ses éléments suivants (next) dans une liste d’Iterators. Dans le concours le Multirator devait toujours choisir la plus petite valeur disponible.

Jusqu’à aujourd’hui, le besoin d’une telle fonctionnalité ne s’est jamais fait sentir dans mes programmes. Or j’en ai justement besoin aujourd’hui. Et au lieux de programmer un Multirator de mon coté et de le garder pour moi seul, je me propose de vous présenter ma démarche.

Lire la suite

Hypothèses sur les données : tri par insertion mémoire ou tri par insertion en fin

Vous connaissez déjà le tri par insertion, de complexité O(nlogn) dans le meilleur des cas et O(n2) dans le pire. Vous savez que c’est le tri utilisé pour ordonner ses cartes au tarot. Mais connaissez-vous sa variante faisant appel à la mémoire ?

Lire la suite