Tri de la structure des données et de la sélection des algorithmes

Le tri par sélection est un algorithme de tri simple. Cet algorithme de tri est un algorithme basé sur une comparaison sur place dans lequel la liste est divisée en deux parties, la partie triée à l'extrémité gauche et la partie non triée à l'extrémité droite. Au départ, la partie triée est vide et la partie non triée est la liste entière.

Le plus petit élément est sélectionné dans le tableau non trié et échangé avec l'élément le plus à gauche, et cet élément devient une partie du tableau trié. Ce processus continue de déplacer la limite de tableau non triée d'un élément vers la droite.

Cet algorithme ne convient pas aux grands ensembles de données car ses complexités moyenne et pire sont de are (n ² ), oùn est le nombre d'éléments.

Comment fonctionne le tri par sélection?

Prenons l'exemple du tableau ci-dessous.

Pour la première position dans la liste triée, la liste entière est balayée séquentiellement. La première position où 14 est actuellement stocké, nous recherchons la liste entière et trouvons que 10 est la valeur la plus basse.

Nous remplaçons donc 14 par 10. Après une itération, 10, qui se trouve être la valeur minimale de la liste, apparaît en première position de la liste triée.

Pour la deuxième position, où 33 réside, nous commençons à balayer le reste de la liste de manière linéaire.

Nous trouvons que 14 est la deuxième valeur la plus basse de la liste et qu'elle devrait apparaître à la deuxième place. Nous échangeons ces valeurs.

Après deux itérations, deux moindres valeurs sont positionnées au début de manière triée.

Le même processus est appliqué au reste des éléments du tableau.

Voici une représentation graphique de l'ensemble du processus de tri -

Maintenant, apprenons quelques aspects de programmation du tri sélectif.

Algorithme

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Pseudocode

procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

Pour en savoir plus sur l'implémentation du tri de sélection dans le langage de programmation C, veuillez cliquer ici .