Français
Menu

Qu'est-ce que Tri stable (stable sort) ?

Tri qui conserve l'ordre relatif d'origine des éléments de même clé. Le tri à bulles, le tri par insertion et le tri fusion sont stables, alors que le tri par sélection, le tri rapide et le tri par tas ne le sont généralement pas. La stabilité est nécessaire pour trier successivement selon plusieurs clés.

Nom japonais: 安定ソート

« Tri stable (stable sort) » apparaît dans 1 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Tri stable (stable sort)

Les enregistrements (nom, note) (A, 80), (B, 70), (C, 80), (D, 70) sont dans cet ordre. Si on les trie par note croissante avec un tri stable, dans quel ordre les noms apparaissent-ils ?

  1. AB, D, A, C
  2. BD, B, A, C
  3. CB, D, C, A
Afficher la réponse et l'explication

Réponse : A. B, D, A, C

Un tri stable conserve l'ordre relatif d'origine des éléments de même clé (ici, la note). B et D, tous deux à 70, restent dans l'ordre B, D, et A et C, tous deux à 80, restent dans l'ordre A, C, ce qui donne B, D, A, C. Le tri à bulles, le tri par insertion et le tri fusion sont stables, alors que le tri par sélection, le tri rapide et le tri par tas ne le sont généralement pas. Avec un tri stable, on peut trier selon plusieurs clés, par exemple trier d'abord par nom, puis par note.

« Tri stable (stable sort) » dans les explications

Questions mentionnant « Tri stable (stable sort) » (1)

  1. Les enregistrements (nom, note) (A, 80), (B, 70), (C, 80), (D, 70) sont dans cet ordre. Si on les trie par note croissante avec un tri stable, dans quel ordre les noms apparaissent-ils ?

Termes associés

Algorithme de Dijkstra Algorithme glouton (greedy) Arbre binaire de recherche (binary search tree) Complexité temporelle (notation grand O) File d'attente Liste chaînée (linked list) Parcours en largeur (breadth-first search) Parcours en profondeur (depth-first search) Pile (stack) Programmation dynamique

Retour au glossaire