Algorithme de tri par sélection avec Python Code Exemple

Par : Sarah Chen Sarah Chen
Hours Le kit de préparation mis à jour

⚡ Résumé intelligent

Le tri par sélection est un algorithme de comparaison sur place qui trie une liste aléatoire par ordre croissant en sélectionnant successivement la plus petite valeur non triée et en la déplaçant dans la section triée. Cette ressource explique… Python exemple et sa complexité temporelle.

  • (I.e. Idée de base : Le tri par sélection recherche de manière répétée la valeur minimale dans la section non triée et la déplace vers la section triée.
  • 🧠 Sur place : Il effectue le tri en utilisant une seule variable temporaire supplémentaire, ce qui donne une complexité spatiale de O(1).
  • ️ Complexité temporelle: Il s'exécute en temps O(n²) dans les pires, les meilleurs et les cas moyens en raison des boucles imbriquées.
  • (I.e. Python Exemple : Une courte fonction avec deux boucles permet d'insérer le minimum à sa place jusqu'à ce que la liste soit triée.
  • ️ Utilisation optimale : Cela convient aux petites listes où le coût d'échange est faible et où chaque valeur doit être vérifiée.
En savoir plus

Algorithme de tri par sélection

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(n2) 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.

[21,6,9,33,3]

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

[3,6,9,21,33]

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

Représentation visuelle

Étape 1)

Représentation visuelle

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

Représentation visuelle

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)

Représentation visuelle

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.

Représentation visuelle

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

Étape 3)

Représentation visuelle

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.

Représentation visuelle

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

Étape 4)

Représentation visuelle

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

Représentation visuelle

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

Étape 5)

Représentation visuelle

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

Représentation visuelle

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

ARTICLES LIÉS

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]

Code Explication

L'explication du code est la suivante

Programme de tri par sélection utilisant Python 3

Voici Code explication:

  1. Définit une fonction nommée selectionSort
  2. 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.
  3. 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
  4. 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.
  5. Trouve la valeur minimale dans la liste non triée et la place à sa bonne position
  6. Met à jour la valeur de minValueIndex lors de l'échangeping La condition est vraie
  7. Compare les valeurs des numéros d'index minValueIndex et i pour voir si elles ne sont pas égales
  8. La valeur la plus à gauche est stockée dans une variable temporelle
  9. La valeur inférieure du côté droit prend la première position
  10. 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
  11. Renvoie la liste triée comme résultat de la fonction
  12. Crée une liste el contenant des nombres aléatoires
  13. 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(n2).

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(n2)
  • Meilleur cas – cela se produit lorsque la liste fournie est déjà triée. L'algorithme effectue le nombre minimal d'exécutions, exprimé par Ω(n).2)
  • Cas moyen – cela se produit lorsque la liste est dans un ordre aléatoire. La complexité moyenne est exprimée par Θ(n) = Θ<sub>big-theta</sub>2)

Le tri par sélection a une complexité spatiale de O(1) car il nécessite une variable temporelle utilisée pour l'échange.ping 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
  • Lorsque le coût de l'échangeping les valeurs sont insignifiantes
  • 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.

FAQ

Le tri par sélection n'est pas stable dans sa forme de base, car l'échangeping L'ordre relatif des éléments distants peut être modifié pour des clés identiques. Une variante utilisant une liste chaînée ou un décalage judicieux permet d'obtenir une structure stable, contrairement à la version standard sous forme de tableau.

Le tri par sélection parcourt la partie non triée pour trouver l'élément minimum et l'insère à sa place, effectuant ainsi peu d'échanges. Le tri par insertion prend chaque élément et décale vers la droite les éléments triés plus grands pour l'insérer. Le tri par insertion est généralement plus rapide sur des données presque triées.

Le tri par sélection effectue au maximum n-1 échanges pour une liste de n éléments, un par passage. Ce faible nombre d'échanges le rend utile lorsque l'écriture en mémoire est coûteuse, même s'il effectue toujours O(n²) comparaisons.

Les tuteurs IA peuvent tracLe tri de sélection se fait étape par étape, chaque échange est animé et un test de complexité temporelle est effectué. Ce retour interactif aide les débutants à comprendre comment le minimum est sélectionné et déplacé à chaque itération.

Oui. Les assistants de programmation IA peuvent générer des tris par sélection dans de nombreux langages, expliquer chaque ligne et suggérer des algorithmes plus efficaces comme le tri rapide lorsque les données d'entrée deviennent volumineuses. Testez toujours le code généré avant de l'utiliser.

Résumez cet article avec :