Algorithmes de Tri

Concepts fondamentaux

Les algorithmes de tri sont des méthodes pour réorganiser une collection d'éléments dans un ordre spécifique. Explorez leurs caractéristiques, visualisez leur fonctionnement et comprenez quand utiliser chaque algorithme.

Algorithmes de Tri

Sélectionnez un algorithme pour voir ses détails

Quand l'utiliser ?

Petits tableaux : Tri par insertion

Grands tableaux : Tri rapide, Tri fusion

Stabilité requise : Tri fusion, Tri à bulles

Mémoire limitée : Tri par tas, Tri rapide

Tableau presque trié : Tri par insertion

Tri à Bulles

Bubble Sort

Stable
Compare et échange les éléments adjacents jusqu'à ce que le tableau soit trié. À chaque passe, le plus grand élément non trié remonte à sa position finale.

Complexité Temporelle

Meilleur cas:O(n)
Cas moyen:O(n²)
Pire cas:O(n²)

Complexité Spatiale

Mémoire auxiliaire:O(1)

Avantages

  • Simple à implémenter
  • Stable
  • Peu de mémoire supplémentaire
  • Détecte si le tableau est déjà trié

Inconvénients

  • Inefficace pour les grands tableaux
  • Complexité quadratique
  • Nombreux échanges inutiles

Implémentation (JavaScript)

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    // Si aucun échange n'a été fait dans cette passe, le tableau est trié
    if (!swapped) break;
  }
  return arr;
}

Le saviez-vous ?

Les navigateurs web modernes utilisent des algorithmes de tri hybrides comme Timsort (combinaison de Merge Sort et Insertion Sort) pour leur méthode Array.sort(), offrant d'excellentes performances dans presque tous les cas.