Informatique & IA · l'expérience
Trier sans tout comparer
Des candidats, des références, un graphe de comparaisons permises et une borne qui tenait depuis 2011. Quatre questions, du débutant à l'expert, sur l'art de trier quand certaines paires ne se comparent pas.
1 · Repère ce qui change
Débutant
Qu'est-ce qui distingue le tri généralisé du tri ordinaire ?
2 · Compte les phases
Chaque phase de l'algorithme fixe une prédiction pour au moins la moitié des liens encore en attente et reporte le reste. Un graphe compte environ un million de liens, soit à peu près 2²⁰.
Intermédiaire
Combien de phases faut-il au plus, environ, pour que chaque lien ait une prédiction ?
3 · Trouve ce qui bloque QuickSort
Expert
Pourquoi ne peut-on pas simplement appliquer une méthode de type QuickSort au tri généralisé ?
4 · Repère ce que l'article ne donne pas
Expert
Lequel de ces résultats l'article ne fournit-il pas ?
Ordre retrouvé
—