Cours Stage - Tri par sélection

Tri par sélection

Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Fiche de cours

Il s'agit d'un tri naïf qui consiste à parcourir la liste afin de chercher le minimum et de l'échanger avec le terme de gauche. 

 

I. Principe de l'algorithme 

 

On considère la liste T suivante :

T = [4, 12, 5, 8, 9, 6, 13, 3]

L'étape 0 consiste à chercher le minimum sur T[0:8] et à l'échanger avec T[0].

A l'issue de cette étape, la liste T sera alors [3, 12, 5, 8, 9, 6, 13, 4]

L'étape 1 consiste à chercher le minimum de la liste mais en ne tenant plus compte de la première valeur, et en cherchant donc dans T[1:8] puis d'échanger le minimum avec T[1]. 

La liste transformée est alors [3, 4, 5, 8, 9, 6, 13, 12].

 

II. Algorithme de tri par sélection

 

Pour écrire l'algorithme du tri, on commence par écrire une fonction permettant de renvoyer la position de la valeur du minimum de T compris entre a et b.

def imin(T, a, b):

     imin = a 

     for i in range(a + 1, b):

          if T[i] < T[imin]:     #dès lors qu'une valeur est inférieure à la valeur d'indice imin,

   

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.