DAA - Tri par sélection

Ce type de tri s'appelle Selection Sortcar il fonctionne en triant les éléments à plusieurs reprises. Cela fonctionne comme suit: trouvez d'abord le plus petit dans le tableau et échangez-le avec l'élément en première position, puis trouvez le deuxième élément le plus petit et échangez-le avec l'élément en deuxième position, et continuez ainsi jusqu'à ce que tout le tableau soit triés.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Le tri par sélection fait partie des techniques de tri les plus simples et fonctionne très bien pour les petits fichiers. Il a une application assez importante car chaque élément est déplacé au plus une fois.

Le tri par section est une méthode de choix pour trier des fichiers avec de très gros objets (enregistrements) et de petites clés. Le pire des cas se produit si le tableau est déjà trié dans un ordre décroissant et que nous voulons les trier dans un ordre croissant.

Néanmoins, le temps requis par l'algorithme de tri par sélection n'est pas très sensible à l'ordre d'origine du tableau à trier: le test si A[j] < min x est exécuté exactement le même nombre de fois dans tous les cas.

Le tri par sélection passe la plupart de son temps à essayer de trouver l'élément minimum dans la partie non triée du tableau. Cela montre clairement la similitude entre le tri par sélection et le tri par bulle.

  • Le tri par bulles sélectionne le maximum d'éléments restants à chaque étape, mais gaspille un peu d'effort pour donner de l'ordre à une partie non triée du tableau.

  • Le tri par sélection est quadratique dans le cas le plus défavorable et le cas moyen et ne nécessite aucune mémoire supplémentaire.

Pour chaque i de 1 à n - 1, il y a un échange et n - i comparaisons, il y a donc un total de n - 1 échanges et

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparaisons.

Ces observations sont valables, quelles que soient les données d'entrée.

Dans le pire des cas, cela pourrait être quadratique, mais dans le cas moyen, cette quantité est O(n log n). Cela implique que lerunning time of Selection sort is quite insensitive to the input.

la mise en oeuvre

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Exemple

Unsorted list:
5 2 1 4 3

1 er itération:

Plus petit = 5

2 <5, le plus petit = 2

1 <2, le plus petit = 1

4> 1, le plus petit = 1

3> 1, le plus petit = 1

Swap 5 et 1
1 2 5 4 3

2 ème itération:

Plus petit = 2

2 <5, le plus petit = 2

2 <4, le plus petit = 2

2 <3, le plus petit = 2

Pas d'échange
1 2 5 4 3

3 ème itération:

Plus petit = 5

4 <5, le plus petit = 4

3 <4, le plus petit = 3

Swap 5 et 3
1 2 3 4 5

4 ème itération:

Plus petit = 4

4 <5, le plus petit = 4

Pas d'échange
1 2 3 4 5

Finalement,

the sorted list is
1 2 3 4 5