Selection Sort (Tri par Sélection)

Le Selection Sort est probablement l'algorithme de tri le plus intuitif qui existe. Lorsqu'on donne un jeu de cartes en désordre à quelqu'un qui n'a jamais étudié l'informatique, il fait naturellement du Selection Sort : il cherche la plus petite carte, la place en premier, puis recommence avec le reste. C'est exactement cela.

Le principe

L'idée est d'une simplicité désarmante :

1. Parcourir le tableau entier pour trouver le minimum.
2. Échanger ce minimum avec l'élément en première position.
3. Répéter l'opération sur le sous-tableau restant (en ignorant les éléments déjà triés).
4. Continuer jusqu'à ce que le tableau soit entièrement trié.

À chaque itération, on "sélectionne" le plus petit élément parmi ceux qui restent — d'où le nom. La partie gauche du tableau grandit d'un élément à chaque passe, et elle est toujours triée.

Exemple pas à pas

Partons du tableau [64, 25, 12, 22, 11].

Passe 1 : Le minimum est 11 (index 4). On l'échange avec 64 (index 0). → [11, 25, 12, 22, 64]

Passe 2 : Sur [25, 12, 22, 64], le minimum est 12 (index 2). On l'échange avec 25. → [11, 12, 25, 22, 64]

Passe 3 : Sur [25, 22, 64], le minimum est 22 (index 3). On l'échange avec 25. → [11, 12, 22, 25, 64]

Passe 4 : Sur [25, 64], le minimum est 25. Il est déjà en place. Rien à faire. → [11, 12, 22, 25, 64]

Le tableau est trié. On effectue exactement n - 1 passes pour un tableau de n éléments.

Implémentation TypeScript

function selectionSort(arr: number[]): number[] {
  const n = arr.length;
 
  for (let i = 0; i < n - 1; i++) {
    // Trouver l'index du minimum dans le sous-tableau arr[i..n-1]
    let minIndex = i;
 
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
 
    // Échanger le minimum trouvé avec le premier élément non trié
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
 
  return arr;
}
 
// Exemple d'utilisation
const tableau = [64, 25, 12, 22, 11];
console.log(selectionSort(tableau));
// → [11, 12, 22, 25, 64]

Une version générique qui accepte un comparateur personnalisé :

function selectionSortGeneric<T>(
  arr: T[],
  compareFn: (a: T, b: T) => number = (a, b) => (a < b ? -1 : a > b ? 1 : 0)
): T[] {
  const n = arr.length;
 
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
 
    for (let j = i + 1; j < n; j++) {
      if (compareFn(arr[j], arr[minIndex]) < 0) {
        minIndex = j;
      }
    }
 
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
 
  return arr;
}
 
// Trier des objets par propriété
const utilisateurs = [
  { nom: "Alice", age: 30 },
  { nom: "Bob", age: 25 },
  { nom: "Charlie", age: 35 },
];
 
selectionSortGeneric(utilisateurs, (a, b) => a.age - b.age);
// → [Bob(25), Alice(30), Charlie(35)]

Complexité O(n²)

Selection Sort est toujours en O(n²), quelles que soient les données en entrée.

Pourquoi ? Pour chaque élément i, on parcourt tous les éléments restants j > i pour trouver le minimum. Cela donne (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparaisons, soit O(n²).

La bonne nouvelle : il effectue au maximum n - 1 échanges (un par passe). C'est bien moins que le Bubble Sort, qui peut faire O(n²) échanges. Quand les échanges sont coûteux — par exemple, lors du déplacement de gros objets en mémoire — Selection Sort a un avantage réel.

Il est aussi en place : il n'a besoin que d'une variable temporaire pour l'échange, donc O(1) en espace. En revanche, il est non stable : deux éléments égaux peuvent voir leur ordre relatif inversé lors d'un échange.

Comparaison avec d'autres algorithmes de tri

Face au Bubble Sort et à l'Insertion Sort, qui ont la même complexité O(n²), le Selection Sort se distingue par son nombre minimal d'échanges. Face aux algorithmes O(n log n) comme Merge Sort ou Quick Sort, il n'y a pas de concurrence pour les grands tableaux.

Quand l'utiliser ?

Soyons honnêtes : dans un code de production sur de grands ensembles de données, Selection Sort n'est presque jamais le bon choix. Mais il a ses cas d'usage légitimes.

Utilisez Selection Sort quand :

• Le tableau est très petit (moins de 10-20 éléments), auquel cas la différence de performance est négligeable.
• Le coût d'un échange est prohibitif : par exemple, des structures volumineuses en mémoire, des éléments sur disque, ou des opérations matérielles coûteuses. Le nombre minimal d'échanges (au plus n-1) devient alors un avantage décisif.
• Vous avez besoin d'un algorithme simple à implémenter et à déboguer pour un contexte embarqué ou éducatif.
• Vous travaillez dans un environnement avec une mémoire très contrainte et ne pouvez pas vous permettre l'overhead de Merge Sort.

Évitez Selection Sort quand :

• Le tableau comporte des milliers d'éléments ou plus — préférez Quick Sort, Merge Sort ou Timsort.
• Vous avez besoin d'un tri stable — optez pour Insertion Sort ou Merge Sort.
• Les données sont déjà presque triées — Insertion Sort sera bien plus efficace (O(n) dans ce cas).

Selection Sort est avant tout un outil pédagogique d'une grande clarté. Il illustre parfaitement les notions de complexité quadratique et la stratégie "trouver le minimum, placer, recommencer". C'est souvent l'un des premiers algorithmes que l'on implémente, et pour cause : il est immédiatement compréhensible par n'importe qui.