18. Selection Sort (Tri par Sélection) : Concept et Implémentation (O(N²))

Le Selection Sort améliore légèrement le Bubble Sort en minimisant le nombre d'échanges.

Concept

Le Selection Sort divise la liste en deux parties : un sous-tableau trié et le sous-tableau non trié restant. Il trouve à plusieurs reprises l'élément minimum dans la partie non triée et le déplace à la fin du sous-tableau trié.

Étapes d'Implémentation

1. Commencer à la première position i.
2. Scanner le reste du tableau (de i+1 à N) pour trouver l'index du plus petit élément (min_idx).
3. Échanger l'élément à la position i avec l'élément à min_idx.
4. Incrémenter i et répéter jusqu'à ce que tout le tableau soit trié.

python def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j

    # Swap the found minimum element with the current element (arr[i])
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr