Tri par sélection : algorithme expliqué avec Python Exemple de code

Qu’est-ce que le tri par sélection ?

TRI DE SÉLECTION est un algorithme de tri par comparaison utilisé pour trier une liste aléatoire d'éléments par ordre croissant. La comparaison ne nécessite pas beaucoup d’espace supplémentaire. Cela ne nécessite qu'un seul espace mémoire supplémentaire pour la variable temporelle.

Ceci est connu comme en place tri. Le tri par sélection a une complexité temporelle de O(n²) où n est le nombre total d'éléments dans la liste. La complexité temporelle mesure le nombre d'itérations nécessaires pour trier la liste. La liste est divisée en deux partitions : la première liste contient les éléments triés, tandis que la seconde liste contient les éléments non triés.

Par défaut, la liste triée est vide et la liste non triée contient tous les éléments. La liste non triée est ensuite analysée pour rechercher la valeur minimale, qui est ensuite placée dans la liste triée. Ce processus est répété jusqu'à ce que toutes les valeurs aient été comparées et triées.

Comment fonctionne le tri par sélection ?

Le premier élément de la partition non triée est comparé à toutes les valeurs du côté droit pour vérifier s'il s'agit de la valeur minimale. Si ce n'est pas la valeur minimale, alors sa position est échangée avec la valeur minimale.

Exemple

Par exemple, si l'index de la valeur minimale est 3, alors la valeur de l'élément d'index 3 est placée à l'index 0 tandis que la valeur qui était à l'index 0 est placée à l'index 3. Si le premier élément de la partition non triée est la valeur minimale, puis il renvoie ses positions.
L'élément qui a été déterminé comme valeur minimale est ensuite déplacé vers la partition de gauche, qui est la liste triée.
Le côté partitionné a maintenant un élément, tandis que le côté non partitionné a (n – 1) éléments où n est le nombre total d'éléments dans la liste. Ce processus est répété encore et encore jusqu'à ce que tous les éléments aient été comparés et triés en fonction de leurs valeurs.

Définition du problème

Une liste d’éléments classés aléatoirement doit être triée par ordre croissant. Considérez la liste suivante comme exemple.

La liste ci-dessus doit être triée pour produire les résultats suivants

Solution (algorithme)

Étape 1) Obtenez la valeur de n qui est la taille totale du tableau

Étape 2) Partitionnez la liste en sections triées et non triées. La section triée est initialement vide tandis que la section non triée contient la liste entière

Étape 3) Choisissez la valeur minimale de la section non partitionnée et placez-la dans la section triée.

Étape 4) Répétez le processus (n – 1) fois jusqu'à ce que tous les éléments de la liste aient été triés.

Représentation visuelle

Étant donné une liste de cinq éléments, les images suivantes illustrent comment l'algorithme de tri par sélection parcourt les valeurs lors de leur tri.

L'image suivante montre la liste non triée

Étape 1)

La première valeur 21 est comparée au reste des valeurs pour vérifier s'il s'agit de la valeur minimale.

3 est la valeur minimale, donc les positions 21 et 3 sont inversées. Les valeurs sur fond vert représentent la partition triée de la liste.

Étape 2)

La valeur 6 qui est le premier élément de la partition non triée est comparée au reste des valeurs pour savoir s'il existe une valeur inférieure.

La valeur 6 est la valeur minimale, elle conserve donc sa position.

Étape 3)

Le premier élément de la liste non triée avec la valeur 9 est comparé au reste des valeurs pour vérifier s'il s'agit de la valeur minimale.

La valeur 9 est la valeur minimale, elle conserve donc sa position dans la partition triée.

Étape 4)

La valeur 33 est comparée au reste des valeurs.

La valeur 21 est inférieure à 33, donc les positions sont inversées pour produire la nouvelle liste ci-dessus.

Étape 5)

Il ne nous reste qu'une seule valeur dans la liste non partitionnée. C’est donc déjà trié.

La liste finale est comme celle présentée dans l'image ci-dessus.

Programme de tri par sélection utilisant Python 3

Le code suivant montre l'implémentation du tri de sélection à l'aide de Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Exécutez le code ci-dessus produit les résultats suivants

[3, 6, 9, 21, 33]

Explication du code

L'explication du code est la suivante

Voici l'explication du code :

Définit une fonction nommée selectionSort
Obtient le nombre total d'éléments dans la liste. Nous en avons besoin pour déterminer le nombre de passes à effectuer lors de la comparaison des valeurs.
Boucle extérieure. Utilise la boucle pour parcourir les valeurs de la liste. Le nombre d'itérations est (n – 1). La valeur de n est 5, donc (5 – 1) nous donne 4. Cela signifie que les itérations externes seront effectuées 4 fois. A chaque itération, la valeur de la variable i est affectée à la variable minValueIndex
Boucle intérieure. Utilise la boucle pour comparer la valeur la plus à gauche aux autres valeurs du côté droit. Cependant, la valeur de j ne commence pas à l'index 0. Elle commence à (i + 1). Cela exclut les valeurs déjà triées afin que nous nous concentrions sur les éléments qui n'ont pas encore été triés.
Trouve la valeur minimale dans la liste non triée et la place à sa bonne position
Met à jour la valeur de minValueIndex lorsque la condition d'échange est vraie
Compare les valeurs des numéros d'index minValueIndex et i pour voir si elles ne sont pas égales
La valeur la plus à gauche est stockée dans une variable temporelle
La valeur inférieure du côté droit prend la première position
La valeur qui était stockée dans la valeur temporelle est stockée dans la position qui était précédemment occupée par la valeur minimale
Renvoie la liste triée comme résultat de la fonction
Crée une liste el contenant des nombres aléatoires
Imprimez la liste triée après avoir appelé la fonction de tri de sélection en passant el comme paramètre.

Complexité temporelle du tri par sélection

La complexité du tri est utilisée pour exprimer le nombre de temps d'exécution nécessaires pour trier la liste. L'implémentation comporte deux boucles.

La boucle externe qui sélectionne les valeurs une par une dans la liste est exécutée n fois où n est le nombre total de valeurs dans la liste.

La boucle interne, qui compare la valeur de la boucle externe avec le reste des valeurs, est également exécutée n fois, n étant le nombre total d'éléments de la liste.

Par conséquent, le nombre d'exécutions est (n * n), qui peut également être exprimé par O(n²).

Le tri de sélection comporte trois catégories de complexité, à savoir :

Pire cas – c’est ici que la liste fournie est par ordre décroissant. L'algorithme effectue le nombre maximum d'exécutions qui est exprimé par [Big-O] O(n²)
Meilleur cas – cela se produit lorsque la liste fournie est déjà triée. L'algorithme effectue le nombre minimum d'exécutions qui est exprimé par [Big-Omega] ?(n²)
Cas moyen – cela se produit lorsque la liste est dans un ordre aléatoire. La complexité moyenne est exprimée par [Big-theta] ?(n²)

Le tri par sélection a une complexité spatiale de O(1) car il nécessite une variable temporelle utilisée pour échanger les valeurs.

Quand utiliser le tri par sélection ?

Le tri par sélection est mieux utilisé lorsque vous souhaitez :

Vous devez trier une petite liste d'éléments par ordre croissant
Quand le coût de l’échange de valeurs est insignifiant
Il est également utilisé lorsque vous devez vous assurer que toutes les valeurs de la liste ont été vérifiées.

Avantages du tri par sélection

Voici les avantages du tri par sélection

Il fonctionne très bien sur les petites listes
Il s'agit d'un algorithme sur place. Cela ne nécessite pas beaucoup d’espace pour le tri. Un seul espace supplémentaire est requis pour contenir la variable temporelle.
Il fonctionne bien sur les articles déjà triés.

Inconvénients du tri par sélection

Voici les inconvénients du tri par sélection.

Il fonctionne mal lorsque vous travaillez sur des listes volumineuses.
Le nombre d'itérations effectuées lors du tri est n au carré, où n est le nombre total d'éléments dans la liste.
D'autres algorithmes, tels que le tri rapide, ont de meilleures performances que le tri par sélection.

Résumé

Le tri par sélection est un algorithme de comparaison sur place utilisé pour trier une liste aléatoire en une liste ordonnée. Il a une complexité temporelle de O(n²)
La liste est divisée en deux sections, triées et non triées. La valeur minimale est sélectionnée dans la section non triée et placée dans la section triée.
Cette chose est répétée jusqu'à ce que tous les éléments aient été triés.
Implémentation du pseudocode dans Python 3 implique l'utilisation de deux boucles for et if pour vérifier si un échange est nécessaire
La complexité temporelle mesure le nombre d'étapes nécessaires pour trier la liste.
La complexité temporelle dans le pire des cas se produit lorsque la liste est classée par ordre décroissant. Il a une complexité temporelle de [Big-O] O(n²)
Dans le meilleur des cas, la complexité temporelle se produit lorsque la liste est déjà par ordre croissant. Il a une complexité temporelle de [Big-Omega] ?(n²)
La complexité temporelle moyenne se produit lorsque la liste est dans un ordre aléatoire. Il a une complexité temporelle de [Big-theta] ?(n²)
Le tri par sélection est mieux utilisé lorsque vous avez une petite liste d’éléments à trier, que le coût d’échange des valeurs n’a pas d’importance et que la vérification de toutes les valeurs est obligatoire.
Le tri par sélection ne fonctionne pas bien sur les listes volumineuses
D'autres algorithmes de tri, tels que le tri rapide, offrent de meilleures performances que le tri par sélection.