Tri par sélection

7.1 Définition du tri par sélection

Le tri par sélection (Selection Sort) est un algorithme de tri qui trouve le plus petit élément de la partie non triée d'un tableau et le swap avec le premier élément de cette partie. Le processus se répète pour les éléments restants, jusqu'à ce que tout le tableau soit trié.

Principe de fonctionnement :

1. On commence avec le premier élément du tableau.
2. On trouve le plus petit élément dans la partie non triée restante du tableau.
3. On swap le plus petit élément avec le premier élément de la partie non triée.
4. On répète le processus pour l'élément suivant, jusqu'à ce que tout le tableau soit trié.

Processus étape par étape

1. On trouve le plus petit élément dans le tableau et on le swap avec le premier élément.
2. On répète le processus pour le tableau restant (en commençant par le deuxième élément).
3. On continue le processus jusqu'à ce que tout le tableau soit trié.

Complexité temporelle et spatiale du tri par sélection

Complexité temporelle :

• Dans le pire des cas : O(n^2) — ça se produit quand les éléments sont initialement disposés dans l'ordre inverse ou de manière aléatoire.
• En moyenne : O(n^2) — ça se produit pour un arrangement aléatoire des éléments.
• Dans le meilleur des cas : O(n^2) — même si le tableau est déjà trié, l'algorithme fait quand même les mêmes comparaisons.

Complexité spatiale :

O(1) — car l'algorithme utilise une quantité constante de mémoire supplémentaire (seulement quelques variables pour stocker des valeurs temporaires).

7.2 Implémentation de l'algorithme de tri par sélection

L'implémentation de l'algorithme est très simple :

Étape 1 : on trouve l'élément minimum parmi tous les éléments et on le swap avec le premier.

Étape 2 : on trouve l'élément minimum parmi tous les éléments sauf le premier, et on le swap avec le deuxième.

Étape 3 : on trouve l'élément minimum parmi tous les éléments sauf le premier et le deuxième, et on le swap avec le troisième.

Implémentation en Python :

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # On trouve l'élément minimum dans la partie non triée restante du tableau
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # On swap l'élément minimum trouvé avec le premier élément de la partie non triée
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr  # On retourne le tableau trié

# Exemple d'utilisation :
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Tableau trié :", sorted_arr)
# Résultat : Tableau trié : [11, 12, 22, 25, 64]

Exemple du fonctionnement de l'algorithme :

1. Premier passage (i = 0) :
   1. On trouve l'élément minimum (11) dans la partie non triée du tableau [64, 25, 12, 22, 11].
   2. On swap 11 avec 64.
   3. Tableau : [11, 25, 12, 22, 64]
2. Deuxième passage (i = 1) :
   1. On trouve l'élément minimum (12) dans la partie non triée du tableau [25, 12, 22, 64].
   2. On swap 12 avec 25.
   3. Tableau : [11, 12, 25, 22, 64]
3. Troisième passage (i = 2) :
   1. On trouve l'élément minimum (22) dans la partie non triée du tableau [25, 22, 64].
   2. On swap 22 avec 25.
   3. Tableau : [11, 12, 22, 25, 64]
4. Quatrième passage (i = 3) :
   1. On trouve l'élément minimum (25) dans la partie non triée du tableau [25, 64].
   2. 25 est déjà à sa place, pas besoin d'échanger.
   3. Tableau : [11, 12, 22, 25, 64]

L'algorithme se termine car tous les éléments sont triés.