Utilisateur:Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua

Voir

• Utilisateur:Suaudeau/Bac à sable/Infobox Algorithme Lua
• Utilisateur:Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua
• Utilisateur:Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 1
• Utilisateur:Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 2
• Module:Infobox/Algorithme
• Module:Wikidata/Documentation

Comparaison entre ancien et nouveau modèle

Tri de Shell

ancien modèle

Tri de Shell

Exemple du tri de Shell avec les espacements 23, 10, 4, 1

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri de Shell

Exemple du tri de Shell avec les espacements 23, 10, 4, 1

Découvreur ou inventeur	Donald Shell (en)
Date de découverte	1959
Problèmes liés	Algorithme de tri, algorithme en place (en), tri par comparaison
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{1.25})$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri de Shell

Exemple du tri de Shell avec les espacements 23, 10, 4, 1

Découvreur ou inventeur	Donald Shell (en)
Date de découverte	1959
Problèmes liés	Algorithme de tri, algorithme en place (en), tri par comparaison
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{1.25})$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(1)$

Tri rapide

ancien modèle

Tri rapide

Quicksort en action sur une liste de nombre aléatoires. Les lignes horizontales sont les valeurs des pivots.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri rapide

Quicksort en action sur une liste de nombres aléatoires. Les lignes horizontales sont les valeurs des pivots.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problèmes liés	Tri par comparaison, diviser pour régner, algorithme de tri

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(n)$
Moyenne	$O(\log n)$

nouveau modèle actuel

Tri rapide

Quicksort en action sur une liste de nombres aléatoires. Les lignes horizontales sont les valeurs des pivots.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problèmes liés	Tri par comparaison, diviser pour régner, algorithme de tri

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(n)$
Moyenne	$O(\log n)$

Tri fusion

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri fusion

Animation du tri par fusion

Découvreur ou inventeur	John von Neumann
Date de découverte	1945
Problèmes liés	Tri par comparaison, tri stable (en)
Structures des données	Tableau, merge algorithm (en)
À l'origine de	Timsort

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(n)$
Meilleur cas	$O(1)$

nouveau modèle actuel

Tri fusion

Animation du tri par fusion

Découvreur ou inventeur	John von Neumann
Date de découverte	1945
Problèmes liés	Tri par comparaison, tri stable (en)
Structures des données	Tableau, merge algorithm (en)
À l'origine de	Timsort

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(n)$
Meilleur cas	$O(1)$

Tri par tas

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri par tas

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.

Découvreur ou inventeur	J. W. J. Williams (en)
Date de découverte	1964
Problème lié	Algorithme de tri
Structure des données	Tableau
À l'origine de	Smoothsort

Complexité en temps

Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri par tas

Une exécution de l'algorithme du tri par tas (Heapsort) trie une partie des valeurs permutées au hasard. Dans un premier temps, les éléments sont réarrangés pour respecter les conditions de tas. Avant le tri à proprement parler, la structure de l'arbre en tas est montrée brièvement par l'illustration.

Découvreur ou inventeur	J. W. J. Williams (en)
Date de découverte	1964
Problème lié	Algorithme de tri
Structure des données	Tableau
À l'origine de	Smoothsort

Complexité en temps

Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace

Pire cas	$O(1)$

Introsort

Pas de modèle présent

ancien modèle

nouveau modèle brouillon

Brouillon!

Introsort

Découvreur ou inventeur	David Musser (en)
Date de découverte	1997
Problèmes liés	Algorithme de tri, hybrid algorithm (en)
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$

nouveau modèle actuel

Introsort

Découvreur ou inventeur	David Musser (en)
Date de découverte	1997
Problèmes liés	Algorithme de tri, hybrid algorithm (en)
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$

Smoothsort

Pas de modèle présent

ancien modèle

nouveau modèle brouillon

Brouillon!

Smoothsort

Smoothsort fonctionnant sur un réseau qui est presque en ordre. Les barres en haut montrent la structure de l'arbre.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1981
Problème lié	Algorithme de tri
Structure des données	Tableau
Basé sur	Tri par tas

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$
Meilleur cas	$O(1)$

nouveau modèle actuel

Smoothsort

Smoothsort fonctionnant sur un réseau qui est presque en ordre. Les barres en haut montrent la structure de l'arbre.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1981
Problème lié	Algorithme de tri
Structure des données	Tableau
Basé sur	Tri par tas

Complexité en temps

Pire cas	$O(n\log n)$
Moyenne	$O(n\log n)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$
Meilleur cas	$O(1)$

Timsort

ancien modèle

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua

Problème lié	Algorithme de tri
Structure des données	Tableau (informatique)

nouveau modèle brouillon

Brouillon!

Timsort

Découvreur ou inventeur	Tim Peters (en)
Date de découverte	2002
Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)
Structure des données	Tableau
Basé sur	Tri fusion, Tri par insertion

Complexité en temps

Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$

nouveau modèle actuel

Timsort

Découvreur ou inventeur	Tim Peters (en)
Date de découverte	2002
Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)
Structure des données	Tableau
Basé sur	Tri fusion, Tri par insertion

Complexité en temps

Pire cas	$O(n\log(n))$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$

Tri arborescent

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri arborescent

Problème lié	Algorithme de tri
Structures des données	Tableau, arbre binaire

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace

Pire cas	$O(n)$

nouveau modèle actuel

Tri arborescent

Problème lié	Algorithme de tri
Structures des données	Tableau, arbre binaire

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n\log(n))$

Complexité en espace

Pire cas	$O(n)$

Tri à peigne

ancien modèle

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri à peigne

Exemple de tri d'une liste de nombres par le tri à peigne.

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log n)$

Complexité en espace

Pire cas	$O(1)$

Tri à bulles

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri à bulles

Tableau de nombres représenté en 2 dimensions : en abscisse la position du nombre dans le tableau, en ordonnée la valeur du nombre. On voit qu'avec le tri à bulles, les grands nombres trouvent leur position finale avant les petits.

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)auxiliary$

nouveau modèle actuel

Tri à bulles

Tableau de nombres représenté en 2 dimensions : en abscisse la position du nombre dans le tableau, en ordonnée la valeur du nombre. On voit qu'avec le tri à bulles, les grands nombres trouvent leur position finale avant les petits.

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)auxiliary$

Tri par insertion

ancien modèle

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, adaptive sort (en), algorithme en place (en), algorithme en ligne
Structure des données	Tableau
À l'origine de	Timsort

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri par insertion

Exemple du tri par insertion utilisant une liste de nombres aléatoires

Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, adaptive sort (en), algorithme en place (en), algorithme en ligne
Structure des données	Tableau
À l'origine de	Timsort

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

Tri par sélection

ancien modèle

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n^{2})$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri par sélection

Exemple du tri par sélection utilisant une liste de nombres aléatoires

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n^{2})$

Complexité en espace

Pire cas	$O(1)$

Tri cocktail

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri cocktail

Problèmes liés	Algorithme de tri, tri stable (en)
Structure des données	Tableau
Basé sur	Tri à bulles

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri cocktail

Problèmes liés	Algorithme de tri, tri stable (en)
Structure des données	Tableau
Basé sur	Tri à bulles

Complexité en temps

Pire cas	$O(n^{2})$
Moyenne	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

Tri stupide

ancien modèle

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problème lié	Algorithme de tri
Structure des données	Liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problèmes liés	Algorithme de tri, Algorithme de Las Vegas
Structure des données	Tableau

Complexité en temps

Pire cas	$\infty$
Moyenne	$O((n+1)!)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$

nouveau modèle actuel

Tri stupide

Avec le tri stupide, un seul mélange peut suffire pour trier les éléments. Cette probabilité est cependant très faible.

Problèmes liés	Algorithme de tri, Algorithme de Las Vegas
Structure des données	Tableau

Complexité en temps

Pire cas	$\infty$
Moyenne	$O((n+1)!)$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(n)$

Tri faire-valoir

ancien modèle

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{log{3}/log{1.5}})$

Complexité en espace

Pire cas	$O(n)$

nouveau modèle actuel

Tri faire-valoir

Visualisation du tri faire-valoir (qui ne montre que les échanges).

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{log{3}/log{1.5}})$

Complexité en espace

Pire cas	$O(n)$

Tri comptage

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri comptage

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n+k)$

Complexité en espace

Pire cas	$O(n+k)$

nouveau modèle actuel

Tri comptage

Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n+k)$

Complexité en espace

Pire cas	$O(n+k)$

Tri par base

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri par base

Découvreur ou inventeur	Herman Hollerith
Date de découverte	1887
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(w\cdot n)$

Complexité en espace

Pire cas	$O(w.n)$

nouveau modèle actuel

Tri par base

Découvreur ou inventeur	Herman Hollerith
Date de découverte	1887
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(w\cdot n)$

Complexité en espace

Pire cas	$O(w.n)$

Tri par paquets

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri par paquets

Problèmes liés	Algorithme, algorithme de tri
Structure des données	Tableau
Basé sur	Pigeonhole sort (en)

Complexité en temps

Pire cas	$O(n^{2})$

Complexité en espace

Pire cas	$O(n\cdot k)$
Moyenne	$O(n+{\frac {n^{2}}{k}}+k)$

nouveau modèle actuel

Tri par paquets

Problèmes liés	Algorithme, algorithme de tri
Structure des données	Tableau
Basé sur	Pigeonhole sort (en)

Complexité en temps

Pire cas	$O(n^{2})$

Complexité en espace

Pire cas	$O(n\cdot k)$
Moyenne	$O(n+{\frac {n^{2}}{k}}+k)$

Tri bitonique

ancien modèle

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Problème lié	Algorithme de tri

nouveau modèle brouillon

Brouillon!

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Découvreur ou inventeur	Ken Batcher
Date de découverte	1968
Problèmes liés	Parallel algorithm (en), algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(\log ^{2}(n))$
Moyenne	$O(\log ^{2}(n))$
Meilleur cas	$O(\log ^{2}(n))$

Complexité en espace

Pire cas	$O(n\log ^{2}(n))$

nouveau modèle actuel

Tri bitonique

Réseau de tri bitonique à huit entrées ; 24 comparateurs, profondeur 6.

Découvreur ou inventeur	Ken Batcher
Date de découverte	1968
Problèmes liés	Parallel algorithm (en), algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(\log ^{2}(n))$
Moyenne	$O(\log ^{2}(n))$
Meilleur cas	$O(\log ^{2}(n))$

Complexité en espace

Pire cas	$O(n\log ^{2}(n))$

Tri pair-impair

ancien modèle

Tri pair-impair par transposition

Exemple de tri d'une liste de nombres par le tri pair-impair.

Problème lié	Algorithme de tri
Structure des données	liste ou tableau

nouveau modèle brouillon

Brouillon!

Tri pair-impair

Exemple de tri d'une liste de nombres par le tri pair-impair.

Découvreur ou inventeur	Nico Habermann (en)
Date de découverte	1972
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

nouveau modèle actuel

Tri pair-impair

Exemple de tri d'une liste de nombres par le tri pair-impair.

Découvreur ou inventeur	Nico Habermann (en)
Date de découverte	1972
Problème lié	Algorithme de tri
Structure des données	Tableau

Complexité en temps

Pire cas	$O(n^{2})$
Meilleur cas	$O(n)$

Complexité en espace

Pire cas	$O(1)$

Tri de crêpes

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Tri de crêpes

Rotation d'une partie de la pile de crêpes à l'aide de la spatule.

Problème lié	Algorithme de tri

nouveau modèle actuel

Tri de crêpes

Rotation d'une partie de la pile de crêpes à l'aide de la spatule.

Problème lié	Algorithme de tri

Recherche dichotomique

ancien modèle

Pas de modèle présent

nouveau modèle brouillon

Brouillon!

Dichotomie

Problèmes liés	Algorithme de recherche, diviser pour régner
Structure des données	Tableau

nouveau modèle actuel

Dichotomie

Problèmes liés	Algorithme de recherche, diviser pour régner
Structure des données	Tableau

exemple

ancien modèle

nouveau modèle brouillon

nouveau modèle actuel