Les Algorithmes de Tri : Complexité et Optimisation

Les questions de ce quiz

1. Quel est le nombre minimum de comparaisons nécessaires pour trier n éléments en utilisant un algorithme basé sur les comparaisons ?

   • Ω(n²)
   • Ω(n)
   • Ω(log n)
   • Ω(n log n)

2. Quel algorithme de tri possède une complexité temporelle moyenne de O(n log n) mais une complexité spatiale de O(log n) grâce à la récursion ?

   • Quick Sort
   • Bubble Sort
   • Heap Sort
   • Merge Sort

3. En utilisant le Counting Sort, quel est le temps nécessaire pour trier un tableau de n éléments avec des valeurs comprises entre 0 et k ?

   • O(n + k)
   • O(n log n)
   • O(k log k)
   • O(n²)

4. Quel est le pire cas de complexité temporelle pour l'algorithme Quicksort et dans quelle situation se produit-il ?

   • O(n²) quand le pivot est toujours le plus petit ou le plus grand élément
   • O(n) quand le pivot est la médiane
   • O(n log n) quand le tableau est déjà trié
   • O(n²) quand le tableau contient des doublons

5. Quel algorithme de tri est stable et garantit une complexité O(n log n) dans tous les cas, au prix d'une complexité spatiale O(n) ?

   • Quick Sort
   • Insertion Sort
   • Heap Sort
   • Merge Sort

6. Quel est le nombre exact de comparaisons effectuées par Bubble Sort dans le meilleur cas (tableau déjà trié) ?

   • n log n
   • n - 1
   • n(n-1)/2
   • 0

7. Quel algorithme utilise une structure de tas (heap) et possède une complexité O(n log n) dans tous les cas sans nécessiter d'espace supplémentaire ?

   • Merge Sort
   • Shell Sort
   • Heap Sort
   • Radix Sort

8. Quel est le nombre minimum de passes nécessaires pour trier un tableau de 8 éléments avec l'algorithme Bubble Sort optimisé (avec détection d'arrêt) dans le pire cas ?

   • 7
   • 4
   • 8
   • 3

9. Quel algorithme de tri non-comparatif est particulièrement efficace pour trier des nombres entiers et fonctionne en O(d × n) où d est le nombre de chiffres ?

   • Shell Sort
   • Bucket Sort
   • Radix Sort
   • Counting Sort

10. Quel est le nombre exact de comparaisons dans le pire cas pour l'algorithme Insertion Sort sur un tableau de n éléments ?

    • n log n
    • 2n - 1
    • n(n-1)/2
    • n - 1

Tu connais les réponses ? Joue pour le savoir.