Tri de sélection: algorithme expliqué avec l'exemple de code Python

Table des matières:

Anonim

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

SELECTION SORT est un algorithme de tri par comparaison utilisé pour trier une liste aléatoire d'éléments dans l'ordre croissant. La comparaison ne nécessite pas beaucoup d'espace supplémentaire. Il ne nécessite qu'un espace mémoire supplémentaire pour la variable temporelle.

C'est ce qu'on appelle le tri sur place . Le tri de sélection a une complexité temporelle de O (n 2 ) 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 des éléments triés, tandis que la seconde liste contient des é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 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.

Dans ce didacticiel sur l'algorithme, vous apprendrez:

  • Qu'est-ce que le tri par sélection?
  • Comment fonctionne le tri par sélection?
  • Définition du problème
  • Solution (algorithme)
  • Représentation visuelle
  • Programme de tri par sélection utilisant Python 3
  • Explication du code
  • Complexité temporelle du tri de sélection
  • Quand utiliser le tri par sélection?
  • Avantages du tri par sélection
  • Inconvénients du tri par sélection

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. S'il ne s'agit pas de la valeur minimale, 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 avec l'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 sur le côté 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 qui sont dans un ordre aléatoire doit être triée par ordre croissant. Considérez la liste suivante à titre d'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 la façon dont l'algorithme de tri par sélection itère dans 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, les positions 21 et 3 sont donc permuté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 si une valeur inférieure existe

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, les positions sont donc permutées pour produire la nouvelle liste ci-dessus.

Étape 5)

Il ne nous reste qu'une seule valeur dans la liste non partitionnée. Par conséquent, il est déjà trié.

La liste finale est comme celle montré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 = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [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:

  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 qui ont déjà été triées afin que nous nous concentrions sur les éléments qui n'ont pas encore été triés.
  5. Recherche la valeur minimale dans la liste non triée et la place dans sa bonne position
  6. Met à jour la valeur de minValueIndex lorsque la condition de permutation 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 a été stockée dans la valeur temporelle est stockée dans la position qui était auparavant détenue par la valeur minimale
  11. Renvoie la liste triée comme résultat de la fonction
  12. Crée une liste el qui a 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 de sélection

La complexité de tri est utilisée pour exprimer le nombre d'exécutions nécessaires pour trier la liste. L'implémentation a 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 où n est le nombre total d'éléments dans la liste.

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

Le tri de sélection a trois catégories de complexité à savoir;

  • Pire des cas - c'est là que la liste fournie est dans l'ordre décroissant. L'algorithme effectue le nombre maximum d'exécutions qui est exprimé par [Big-O] O (n 2 )
  • 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 2 )
  • Cas moyen - cela se produit lorsque la liste est dans un ordre aléatoire. La complexité moyenne est exprimée par [Big-theta] ⊝ (n 2 )

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

Quand utiliser le tri par sélection?

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

  • Vous devez trier une petite liste d'articles par ordre croissant
  • Lorsque 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 sélectif

  • Il fonctionne très bien sur les petites listes
  • C'est un algorithme en place. Il ne nécessite pas beaucoup d'espace pour le tri. Un seul espace supplémentaire est nécessaire pour contenir la variable temporelle.
  • Il fonctionne bien sur les éléments qui ont déjà été 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 d'énormes listes.
  • Le nombre d'itérations effectuées lors du tri est de n-carré, où n est le nombre total d'éléments de la liste.
  • D'autres algorithmes, tels que le tri rapide, ont de meilleures performances par rapport au 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 2 )
  • 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.
  • L'implémentation du pseudocode dans Python 3 implique l'utilisation de deux boucles for et des instructions if pour vérifier si l'é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 dans l'ordre décroissant. Il a une complexité temporelle de [Big-O] O (n 2 )
  • La complexité temporelle dans le meilleur des cas se produit lorsque la liste est déjà dans l'ordre croissant. Il a une complexité temporelle de [Big-Omega] Ω (n 2 )
  • La complexité temporelle moyenne se produit lorsque la liste est dans un ordre aléatoire. Il a une complexité temporelle de [Big-theta] ⊝ (n 2 )
  • Le tri par sélection est mieux utilisé lorsque vous avez une petite liste d'éléments à trier, le coût de l'échange de valeurs n'a pas d'importance et la vérification de toutes les valeurs est obligatoire.
  • Le tri par sélection ne fonctionne pas bien sur de grandes listes
  • D'autres algorithmes de tri, tels que le tri rapide, ont de meilleures performances par rapport au tri par sélection.