Programme C pour le tri par sélection

Le tri par sélection est un algorithme agressif qui fonctionne en trouvant le plus petit nombre d'un tableau et en le plaçant en première position. Le prochain tableau à parcourir commencera au prochain index où se trouve le plus petit nombre.

Prenons un exemple pour illustrer plus clairement ce concept.

Nous avons un tableau {6, 3, 8, 12, 9} et le plus petit élément de ce tableau est 3. Nous mettons donc 3 en première position et après cela, le tableau ressemblera à {3, 6, 8, 12, 9} . Nous allons maintenant retrouver le plus petit nombre, mais cette fois nous ne considérerons pas 3 dans la recherche puisqu'il est à sa place. Recherchez le plus petit élément suivant, 6, créez un tableau contenant 6 à la deuxième position et recherchez à nouveau dans le tableau jusqu'à ce que le tableau soit trié.

Fonctionnement de l'algorithme de tri par sélection -

L'algorithme de tri par sélection suit les étapes suivantes

Prenons un tableau {20, 12, 23, 55,21}

• Définissons le premier élément du tableau à la valeur minimale .

  Valeur minimale = 20

• Comparez la valeur minimale avec l'élément suivant et si elle est inférieure à la valeur minimale, attribuez cet élément comme valeur minimale. Faites cela jusqu'à la fin du tableau.

  est comparé à 12 : 20 > 12, la valeur minimale = 12

  est comparé à 23 : 12 est comparée à 55 : 12

  est comparé à 21 : 12

• met la valeur minimale à la première position (index 0) du tableau.

  Array = {12, 20,23, 55, 21}

• Pour la prochaine itération, commencez le tri à partir du premier élément non trié.

  Array = {12, 20,23, 55, 21}

  Commencez la recherche à partir de 20 et placez ensuite l'élément avec la valeur minimale.

  Itération 2 :

  valeur minimale = 20

  par rapport à 23 : 20

  par rapport à 55 : 20

  par rapport à 21 : 20

  la valeur minimale reste inchangée,

  tableau = {12, 20,23, 55, 21}

  Itération 3 :

  valeur minimale = 23.

  par rapport à 55 : 23

  par rapport à 21 : 23 > 21, valeur minimale = 21

  valeur minimale déplacée vers l'index = 2

  Array = {12, 20, 21, 55, 23}

  Itération 4 :

  minimum = 55

  par rapport à 23 : 23

  minimum déplacé vers l'index 3 Tableau = { 12 , 20 , 21 , 23 , 55 }

Exemple

#include <stdio.h>
int main() {
   int arr[10]={6,12,0,18,11,99,55,45,34,2};
   int n=10;
   int i, j, position, swap;
   for (i = 0; i < (n - 1); i++) {
      position = i;
      for (j = i + 1; j < n; j++) {
         if (arr[position] > arr[j])
            position = j;
      }
      if (position != i) {
         swap = arr[i];
         arr[i] = arr[position];
         arr[position] = swap;
      }
   }
   for (i = 0; i < n; i++)
      printf("%d\t", arr[i]);
   return 0;
}

Sortie

0 2 6 11 12 18 34 45 55 99

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!