Tri par sélection

Tri par sélection du minimum.

L=[45, 2, 4, 6, -5, 4, 3]
L=[ -5, 2, 4, 6, 45, 4, 3 ]
L=[ -5, 2, 4, 6, 45, 4, 3 ]
L=[ -5, 2, 3 , 6, 45, 4, 4 ]
A ce stade, on a deux choix. Supposons que l'on choisisse la première occurrence de 4 :
L=[ -5, 2, 3, 4 , 45, 6, 4 ]
L=[ -5, 2, 3, 4, 4 , 6, 45 ]
L=[ -5, 2, 3, 4, 4, 6 , 45 ]
L=[ -5, 2, 3, 4, 4, 6, 45 ]

Tri par sélection du maximum.

Entrée : une liste d'éléments comparables.
Sortie : la liste triée en ordre croissant.

Traitement :
	1. On colore en noir tous les éléments.
	2. On repère un élément de valeur maximale parmi les éléments noirs.
	3. On échange cet élément avec l'élément en queue des éléments noirs puis on le colore en rouge.
	4. On reprend au point 2 tant qu'il reste des noirs.
  

L=[45, 2, 4, 6, -5, 4, 3]
L=[ 3, 2, 4, 6,-5, 4, 45]
L=[ 3, 2, 4, 4,-5 6, 45]
On a ici deux choix possibles. Supposons que l'on fasse le suivant :
L=[ 3, 2, -5, 4, 4, 6, 45]
L=[ 3, 2, -5, 4, 4, 6, 45]
L=[ -5, 2, 3, 4, 4, 6, 45]
L=[ -5, 2, 3, 4, 4, 6, 45]
L=[ -5, 2, 3, 4, 4, 6, 45]

Terminaison

A chaque étape, un nouvel élément devient rouge. Comme il n'y a qu'un nombre fini d'éléments, ils finiront par être tous rouges. Or le critère d'arrêt est justement "ils sont tous rouges" (ou, cela revient au même, "il n'y a plus de noirs"). L'algorithme terminera donc effectivement.

Invariant de boucle

La propriété à vérifier (la liste rouge est triée et tout noir est ≥ tout rouge) est clairement vérifiée lorsque la liste rouge contient 0 ou 1 élément.

Supposons que cette propriété est vérifiée lorsque la liste rouge contient i éléments.
On a donc L= [ rouge₁, rouge₂, ..., rouge_i, noir₁, noir₂, ..., noir_n-i ]
avec rouge₁ ≤ rouge₂≤ ...≤ rouge_i≤ min(noir₁, noir₂, ..., noir_n-i).

Soit k un indice (entre 1 et n-i) tel que noir_k = min(noir₁, noir₂, ..., noir_n-i).

A l'étape suivante, la liste L devient :
L= [ rouge₁, rouge₂, ..., rouge_i, rouge_i+1 = noir_k, noir₁, noir₂, ..., noir_k-1, noir_k+1, ... , noir_n-i ]
Il est clair que l'on a rouge₁ ≤ rouge₂≤ ...≤ rouge_i≤ rouge_i+1≤ min(noir₁, noir₂, ..., noir_k-1, noir_k+1, ... , noir_n-i).

La propriété est donc établie.

Correction.

Lorsque l'algorithme termine, la liste est entièrement rouge : elle est donc triée d'après ce qui précède.

from random import randint


# création d'une liste d'entiers au hasard
# pour tester la fonction de tri :
lg=15
L = [ randint(1,100) for j in range(lg)]


def rechercheMin(L,i) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		if L[k]<mini :
			indiceDuMini, mini = k, L[k]
	return indiceDuMini
			

def triselection(L) :
	for i in range( len(L) -1 ) :
		indiceDuMini=rechercheMin(L,i)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	
		
print('L avant tri :\n ', L)
triselection(L)
print('L après tri :\n ', L)

Nombre de comparaisons

Les comparaisons entre éléments de la liste se font dans la fonction rechercheMin.

def rechercheMin(L,i) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		if L[k]<mini :
			indiceDuMini, mini = k, L[k]
	return indiceDuMini 

Dans cette fonction, on compare les éléments L[i+1], L[i+2], ..., L[len(L)-1] à une valeur mini (qui est une valeur de la liste qui évolue au cours du déroulement).
Le nombre de comparaisons est, dans cette fonction, égal à len(L)-1-i = n-1-i en notant n la longueur de la liste à trier.

Cette fonction est appelée dans la procédure triselection.

def triselection(L) :
	for i in range( len(L) -1 ) :
		indiceDuMini=rechercheMin(L,i)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]

Elle est appelée avec les valeurs de i : 0, 1, 2, ..., len(L)-2.

Le nombre total de comparaisons est donc : \[ C_n = \sum_{i=0}^{n-2} (n-1-i) \] \[ C_n = (n-1)+(n-2)+(n-3)+ \dots + 1 \] On reconnaît là une progression arithmétique : \[ C_n = \frac{1}{2} n (n-1) \]

Nombre d'échanges

Les échanges entre deux éléments de la liste se font dans la procédure triselection. Il y en a un pour chacune des valeurs de i de la boucle de cette procédure (i=0, 1, 2, ..., n-2). Il y a donc n-2 échanges (le nombre d'échanges « réels » peut être inférieur puisqu'on peut avoir indiceDuMini=i lors du déroulement).

Nombre d'affectations

Les affectations que l'on n'a pas déjà comptées dans les échanges ci-dessus se font dans la fonction rechercheMin.
Il y en a au plus 2(n-i).
Comme cette fonction rechercheMin est appelée par la fonction triselection pour les valeurs i = 0, 1, 2, ..., n-2, le nombre de ces affectations est d'au plus : \[ A_n = \sum_{i = 0}^{n-2} 2\times(n-i) \] \[A_n = 2\times (n+(n-1)+(n-2)+\dots + 2) \] soit \[A_n = (n-1)(n-2)\]

Temps de calcul

On part de l'idée (à peu près correcte) que toute comparaison demandera toujours le même temps c, toute affectation le même temps a, tout échange d'éléments dans la liste le même temps e.

On a donc un temps d'exécution total majoré par : \[ T_n = c\times \frac{1}{2} n (n-1) + e \times (n-2) + a \times (n-1)(n-2) \] et (les comparaisons étant effectuées systématiquement) minoré par \[ T_n = c\times \frac{1}{2} n (n-1) \] Le temps d'exécution est donc compris entre deux polynômes de degré deux. On a ainsi établi l'affirmation de la page de cours (complexité temporelle quadratique).

Décompte expérimental du nombre de comparaison.

Nous demandons une fonction qui à n, longueur de liste, associe le nombre de comparaisons pour trier cette liste. Nous verrons que pour d'autres tris la demande n'a pas nécessairement de sens (le nombre de comparaisons pouvant dépendre de la longueur de la liste mais aussi de l'agencement initial des éléments dans la liste).

from random import randint


# création d'une liste d'entiers au hasard
# pour tester la fonction de tri :
lg=20
L = [ randint(1,100) for j in range(lg)]


def rechercheMin(L,i, nbComparaison) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		nbComparaison+=1 # on compte la comparaison faite
						 # dans le test if L[k]<mini 
		if L[k]< mini :			
			indiceDuMini, mini = k, L[k]
	return indiceDuMini, nbComparaison
			

def triselection(L, nbComparaison = 0) :
	for i in range( len(L) -1 ) :
		indiceDuMini, nbComparaison = rechercheMin(L,i, nbComparaison)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	return nbComparaison
	
		
 

print(triselection(L))
# comparaison avec la formule déterminée précédemment :
print(1/2*lg*(lg-1))

Représentation graphique

Dans la première version ci-dessous, on représente le nombre de comparaisons en fonction de la taille de la liste de départ.

from random import randint
from pylab import plot, show

def creationListe( n ) :
	""" crée une liste de n éléments, 
	éléments au hasard entre 1 et 2n."""
	return [ randint(1,2*n) for j in range(n)]


def rechercheMin(L,i, nbComparaison) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		nbComparaison+=1 # on compte la comparaison faite
						 # dans le test if L[k]<mini 
		if L[k]<mini :			
			indiceDuMini, mini = k, L[k]
	return indiceDuMini, nbComparaison
			

def triselection(L, nbComparaison = 0) :
	""" trie la liste suivant le tri par sélection."""
	for i in range( len(L) -1 ) :
		indiceDuMini, nbComparaison = rechercheMin(L,i, nbComparaison)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	return nbComparaison
	
		
# liste de tailles de listes :
TailleListe = range(50, 2000, 30)
# liste des nombres d'opérations associés :
NbComparaisonTri = [ triselection(creationListe(n)) for n in TailleListe ]
# graphe des nombres de comparaisons (axe Oy) en fonction
# des tailles de listes (axe Ox) :
plot(TailleListe, NbComparaisonTri)
# on lance une visualisation de la courbe :
show()

On obtient :

Dans la version ci-dessous, on lance sur le même graphique la représentation graphique de la fonction n ↦ 0.5*n*(n-1).

from random import randint
from pylab import plot, show

def creationListe( n ) :
	""" crée une liste de n éléments, 
	éléments au hasard entre 1 et 2n."""
	return [ randint(1,2*n) for j in range(n)]


def rechercheMin(L,i, nbComparaison) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		nbComparaison+=1 # on compte la comparaison faite
						 # dans le test if L[k]<mini 
		if L[k]<mini :			
			indiceDuMini, mini = k, L[k]
	return indiceDuMini, nbComparaison
			

def triselection(L, nbComparaison = 0) :
	""" tri la liste suivant le tri par sélection."""
	for i in range( len(L) -1 ) :
		indiceDuMini, nbComparaison = rechercheMin(L,i, nbComparaison)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	return nbComparaison
	
		
# liste de tailles de listes :
TailleListe = range(50, 2000, 30)
# liste des nombres d'opérations associés :
NbComparaisonTri = [ triselection(creationListe(n)) for n in TailleListe ]
# liste des nb de comparaisons obtenus par le calcul de l'exo précédent :
NbComparaisonTheoriq = [ int(1/2*n*(n-1)) for n in TailleListe ]
# graphe des nombres d'opérations (axe Oy) en fonction
# des tailles de listes (axe Ox)  en rouge pointillés ('r--')
# et graphe de la fonction n->0.5*n*(n-1) en étoiles bleues ('b*')
plot(TailleListe, NbComparaisonTri, 'r--', TailleListe, NbComparaisonTheoriq,'b*')
# on lance une visualisation des s courbes :
show()

Les deux courbes se superposent comme attendu.

Contrôle expérimental de la nature de la courbe.

Avec le programme ci-dessous :

from random import randint
from pylab import plot, show, polyfit

def creationListe( n ) :
	""" crée une liste de n éléments, 
	éléments au hasard entre 1 et 2n."""
	return [ randint(1,2*n) for j in range(n)]


def rechercheMin(L,i, nbComparaison) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	 
	for k in range( i+1, len(L) ) :
		nbComparaison+=1 # on compte la comparaison faite
						 # dans le test if L[k]<mini 
		if L[k]<mini :			
			indiceDuMini, mini = k, L[k]
	return indiceDuMini, nbComparaison
			

def triselection(L, nbComparaison = 0) :
	""" tri la liste suivant le tri par sélection."""
	for i in range( len(L) -1 ) :
		indiceDuMini, nbComparaison = rechercheMin(L,i, nbComparaison)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	return nbComparaison
	
		
# liste de tailles de listes :
TailleListe = range(50, 2000, 30)
# liste des nombres d'opérations associés :
NbComparaisonTri = [ triselection(creationListe(n)) for n in TailleListe ]
# polynôme de degré 2 au plus près de la courbe (TailleListe,NbComparaisonTri) :
p=polyfit(TailleListe,NbComparaisonTri,2)
OrdonneePoly = [ p[0]*x**2+p[1]*x+p[2] for x in TailleListe ] 
# affichage du polynôme :
print(" p(x) = {}*x^2+{}*x+{}.".format(p[0], p[1],p[2] ) )
# graphe (TailleListe,NbComparaisonTri)   en rouge pointillés ('r--')
# et graphe (TailleListe, p(x) )  en étoiles bleues ('b*')
plot(TailleListe, NbComparaisonTri, 'r--', TailleListe, OrdonneePoly ,'b*')
# on lance une visualisation des courbes :
show()

On obtient pour le polynôme :

p(x) = 0.5000000000000008*x^2+-0.5000000000007333*x+9.131883202823179e-11

c'est à dire quasiment (compte tenu des inévitables problèmes dus aux transcriptions des nombres réels en nombres machines), la formule calculée manuellement x ↦ 0.5*x*(x-1) lors de l'exercice précédent.

Et graphiquement, on obtient deux courbes qui semblent se superposer (ce qui confirme que le nombre de comparaisons est approximativement une fonction du second degré).

from random import randint
from time import time
from pylab import plot, show, polyfit

def creationListe( n ) :
	""" crée une liste de n éléments, 
	éléments au hasard entre 1 et 2n."""
	return [ randint(1,2*n) for j in range(n)]


def rechercheMin(L,i) :
	""" retourne l'indice d'un élément minimal
	parmi les éléments L[i], L[i+1], L[i+2] ..."""
	indiceDuMini, mini = i, L[i]
	for k in range( i+1, len(L) ) :
		if L[k]<mini : indiceDuMini, mini = k, L[k]
	return indiceDuMini
			

def triselection(L) :
	""" tri la liste suivant le tri par sélection
	et retourne le temps d'exécution."""
	start=time()
	for i in range( len(L) -1 ) :
		indiceDuMini = rechercheMin(L,i)
		L[i], L[indiceDuMini] = L[indiceDuMini], L[i]
	return time()-start
	
		
# liste de tailles de listes :
TailleListe = range(50, 10000, 200)
# liste des temps d'exécution :
TempsTri = [ triselection(creationListe(n)) for n in TailleListe ]
# approximation par polynôme second degré :
p=polyfit(TailleListe, TempsTri, 2)
Yp= [ p[0]*x**2+p[1]*x+p[2] for x in TailleListe ]
# courbes  (taille de la liste, Temps d'exécution) 
# et (taille de la liste, polynôme second degré approchant) :
plot(TailleListe, TempsTri,'r--',TailleListe, Yp, 'b*')
# on lance une visualisation de la courbe :
show()

On obtient la figure suivante qui confirme un temps fonction du second degré en la taille de la liste d'entrée :

Modification.
Lorsqu'on parcourt la liste noire, on n'attend pas d'avoir trouver un minimum parmi les noirs pour l'échange avec la tête noire. On effectue l'échange entre la tête noire et un noir visité inférieur à la tête noire à chaque fois que l'on rencontre un tel noir inférieur à la tête noire.

Un codage possible :

from random import randint


# création d'une liste d'entiers au hasard
# pour tester la fonction de tri :
lg= randint(5, 15) # longueur de liste au hasard
L = [ randint(1,100) for j in range(lg) ]



def triselection(L) :
	for i in range( len(L) -1 ) :
		for j in range( i+1, len(L) ) :
			if L[j] < L[i] :
				L[i], L[j] = L[j], L[i]
	
		
print('L avant tri :\n ', L)
triselection(L)
print('L après tri :\n ', L)

Voir le code du fichier !