Quels types de tri connaissez-vous et quelles sont leurs difficultés en termes de temps et de mémoire?

Il existe de nombreux algorithmes de tri, voici les principaux avec leur complexité temporelle et spatiale :

• Tri à bulles (Bubble Sort)

  • Temps : O(n²) dans le pire et le cas moyen
  • Mémoire : O(1) (tri en place)

• Tri par insertion (Insertion Sort)

  • Temps : O(n²) dans le pire cas, O(n) dans le meilleur (tableau presque trié)
  • Mémoire : O(1)

• Tri par sélection (Selection Sort)

  • Temps : O(n²) dans tous les cas
  • Mémoire : O(1)

• Tri par fusion (Merge Sort)

  • Temps : O(n log n) dans tous les cas
  • Mémoire : O(n) (nécessite une mémoire supplémentaire pour la fusion)

• Tri rapide (Quick Sort)

  • Temps : O(n log n) en moyenne, O(n²) dans le pire cas (rare)
  • Mémoire : O(log n) (pile récursive)

• Tri par tas (Heap Sort)

  • Temps : O(n log n) dans tous les cas
  • Mémoire : O(1)

• Timsort — tri hybride utilisé en Python et Java

  • Temps : O(n log n) en moyenne et dans le pire cas
  • Mémoire : O(n)

Le choix de l'algorithme dépend de la taille des données, des exigences en mémoire et de la stabilité du tri (si il conserve l'ordre des éléments égaux). Par exemple, Merge Sort est stable, Quick Sort est généralement plus rapide mais instable.