Français
Menu

Structures de données et algorithmes

On trie par ordre croissant le tableau 5, 3, 8, 1, 4 avec le tri à bulles. Quel est le tableau après une passe, au cours de laquelle les éléments voisins sont comparés du début jusqu'à la fin et échangés chaque fois que celui de gauche est le plus grand ?

  1. A1, 3, 8, 5, 4
  2. B3, 5, 1, 4, 8
  3. C1, 3, 4, 5, 8
Afficher la réponse et l'explication

Réponse : B. 3, 5, 1, 4, 8

L'échange de 5 et 3 donne 3, 5, 8, 1, 4 ; 5 et 8 restent en place ; l'échange de 8 et 1 donne 3, 5, 1, 8, 4 ; et l'échange de 8 et 4 donne 3, 5, 1, 4, 8. Une passe amène la valeur maximale, 8, jusqu'à la fin, où sa position est définitive, et la passe suivante trie de la même façon les quatre éléments restants. 1, 3, 8, 5, 4 est le tableau après une passe du tri par sélection, qui place le minimum en tête par un échange, et 1, 3, 4, 5, 8 est le résultat entièrement trié.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. On trie par ordre croissant le tableau 29, 10, 14, 37, 13 avec le tri par sélection, qui cherche le minimum de la partie non triée et l'échange avec le premier élément de cette partie. Quel est le tableau après deux répétitions de cette étape ?
  2. On trie par ordre croissant un tableau de 10 éléments avec le tri par insertion. Chaque élément à partir du deuxième est extrait et comparé aux éléments situés à sa gauche, en commençant par son voisin de gauche, jusqu'à trouver un élément inférieur ou égal ou jusqu'à atteindre le début. Combien de comparaisons sont effectuées quand le tableau est déjà dans l'ordre croissant, et quand il est dans l'ordre décroissant ?
  3. Quel algorithme de tri a une complexité temporelle en O(n log n) même dans le pire cas et trie presque sans mémoire supplémentaire, comme un tableau de travail ?
  4. 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 ?
  5. Quel est le cas typique dans lequel la complexité temporelle du tri rapide devient O(n²) ?