Français
Menu

Structures de données et algorithmes

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 ?

  1. A45 dans les deux cas
  2. B10 et 100
  3. C9 et 45
Afficher la réponse et l'explication

Réponse : C. 9 et 45

Si le tableau est déjà croissant, chaque élément ne demande qu'une comparaison avec son voisin de gauche, soit 9 comparaisons au total pour les 9 éléments. S'il est décroissant, le i-ème élément extrait est comparé aux i éléments situés à sa gauche, soit 1 + 2 + … + 9 = 45. Le tri par insertion varie donc beaucoup selon l'entrée, O(n) dans le meilleur cas et O(n²) dans le pire, et il est très rapide sur des données presque triées. Le tri de Shell en tire parti en appliquant d'abord le tri par insertion à des éléments espacés d'un certain pas, et Timsort utilise aussi le tri par insertion pour les courtes séquences.

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

Autres questions sur Structures de données et algorithmes

  1. 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 ?
  2. 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 ?
  3. Quel est le cas typique dans lequel la complexité temporelle du tri rapide devient O(n²) ?
  4. Dans le tri fusion, on fusionne les deux séquences triées 1, 4, 7, 9 et 2, 3, 8, 10 en une seule en comparant de façon répétée leurs éléments de tête et en sortant le plus petit. Quand une séquence est vide, le reste de l'autre est sorti sans comparaison. Combien de comparaisons sont effectuées ?
  5. Un tas binaire est stocké dans un tableau a[0], a[1], a[2], … avec la racine en a[0], en remplissant chaque niveau de gauche à droite à partir du haut. Quels sont les enfants et le parent de a[4] ?