Français
Menu

Structures de données et algorithmes

Quel est le cas typique dans lequel la complexité temporelle du tri rapide devient O(n²) ?

  1. ALes données sont dans un ordre aléatoire et le pivot est choisi au hasard
  2. BLe nombre de données est une puissance de deux
  3. CLes données sont déjà triées et le premier élément est toujours pris comme pivot
Afficher la réponse et l'explication

Réponse : C. Les données sont déjà triées et le premier élément est toujours pris comme pivot

Le tri rapide répartit les éléments entre ceux qui sont plus petits et ceux qui sont plus grands que le pivot, puis découpe à nouveau chaque partie. Si les données sont déjà triées et que le premier élément est toujours le pivot, celui-ci est à chaque fois le minimum et chaque découpage est déséquilibré, avec zéro élément d'un côté et tout le reste de l'autre : le tri effectue alors n(n−1)/2 comparaisons (4950 pour n = 100). Choisir le pivot au hasard ou comme médiane de trois valeurs rend une longue suite de découpages déséquilibrés extrêmement improbable. Le nombre de données n'a aucune incidence sur la complexité temporelle.

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

Autres questions sur Structures de données et algorithmes

  1. 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 ?
  2. 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] ?
  3. Un tas max, dans lequel la valeur de chaque parent est supérieure ou égale à celles de ses enfants, est stocké dans un tableau avec la racine en a[0]. On ajoute 45 au tas 50, 30, 40, 10, 20, 35 en le plaçant à la fin, puis en l'échangeant avec son parent tant qu'il est plus grand que celui-ci. Quel est le tableau obtenu ?
  4. Quand on parcourt un arbre binaire de recherche dans l'ordre infixe (sous-arbre gauche, puis le nœud, puis sous-arbre droit), dans quel ordre se présentent les valeurs des nœuds visités ? On suppose toutes les valeurs distinctes.
  5. On insère dans cet ordre les valeurs 50, 30, 70, 20, 40, 60, 80 dans un arbre binaire de recherche vide. Dans quel ordre les nœuds sont-ils visités quand on parcourt l'arbre dans l'ordre postfixe (sous-arbre gauche, sous-arbre droit, puis le nœud) ?