⚡

Tri par comparaisons

Chapitre 8 • Sélection, Bulles, Insertion & Tri rapide

Statut : Prêt à jouer
Chapitre 8

Tri par comparaisons

Étude des algorithmes de tri par comparaisons : tri par sélection, tri à bulles, tri par insertion, et tri rapide (Quicksort), avec analyses de complexité en comparaisons et affectations.

Quel est le titre exact du chapitre 8 ?

#1/15

Quelles sont les deux opérations fondamentales des algorithmes présentés dans ce chapitre ?

#2/15

Quel est le principe de base du tri par sélection ?

#3/15

Quelle est la complexité asymptotique en nombre de comparaisons du tri par sélection dans le pire des cas {pire}(n)$ ?

#4/15

Combien d'affectations (via la fonction échange) le tri par sélection effectue-t-il au total pour un tableau de taille $ ?

#5/15

Quel est le principe fondamental du tri à bulles ?

#6/15

Quelle est la complexité du tri à bulles en nombre de comparaisons dans le pire des cas ?

#7/15

Dans le pire des cas pour le nombre d'affectations (lorsque le tableau est ordonné par ordre décroissant), quelle est la complexité du tri à bulles ?

#8/15

Quelle est la complexité en moyenne du nombre d'affectations pour le tri à bulles (en supposant des éléments distincts et équiprobables) ?

#9/15

À quelle situation de la vie courante le tri par insertion est-il comparé ?

#10/15

Quelles sont les complexités dans le pire des cas du tri par insertion (pour les comparaisons et les affectations) ?

#11/15

Quel est le principe général de l'algorithme du tri rapide (Quicksort) ?

#12/15

Que fait la fonction partitionner dans l'algorithme du tri rapide ?

#13/15

Dans l'exemple du cours avec = [10, 11, 3, 6, 4, 2]$, quelle valeur est renvoyée par le tout premier appel à partitionner$(t, 0, 5)$ ?

#14/15

Que se passe-t-il lors de l'appel récursivement généré rapide$(t, 5, 5)$ dans le cours ?

#15/15