Formation I.S.N.

Tri par sélection : programmation Python

programmation du tri par sélection.

Écrire une fonction Python triant une liste par le principe de sélection du minimum.

On triera la liste sur place (pas de création de liste intermédiaire dans les étapes, et c'est la liste initiale qui est modifiée).

  • un code possible
  • avec traces

from random import randint # pour créer une liste au hasard

def indice_du_min(liste, depart):
	"""
	renvoie l'indice d'une valeur minimale 
	parmi liste[depart], liste[depart+1], liste[depart+2], ..., liste[len(liste)-1]
	"""
	valeur_min = liste[depart]
	indice = depart
	for i in range(depart+1, len(liste)):
		if liste[i] < valeur_min :
			valeur_min, indice = liste[i], i
	return indice


def tri_selection(liste) :
	for i in range(len(liste)-1):
		m = indice_du_min(liste, i)
		liste[i], liste[m] = liste[m], liste[i]
		
		
		
L = [randint(100,999) for i in range(randint(6,12))]
print("Liste avant le tri : ", L)
tri_selection(L)
print("\nListe après le tri : ", L)

Pour ceux qui aiment la concision : 


from random import randint # pour créer une liste au hasard
 

def tri_selection(liste) :
	for i in range(len(liste)-1):
		m = min((liste[k], k) for k in range(i, len(liste)))[1]
		liste[i], liste[m] = liste[m], liste[i]



		
L = [randint(100,999) for i in range(randint(6,12))]
print("Liste avant le tri : ", L)
tri_selection(L)
print("\nListe après le tri : ", L)			
	

from random import randint # pour créer une liste au hasard

def indice_du_min(liste, depart):
	"""
	renvoie l'indice d'une valeur minimale
	parmi liste[depart], liste[depart+1], liste[depart+2], ..., liste[len(liste)-1]
	"""
	valeur_min = liste[depart]
	indice = depart
	for i in range(depart+1, len(liste)):
		if liste[i] < valeur_min :
			valeur_min, indice = liste[i], i
	return indice


def tri_selection(liste) :
	for i in range(len(liste)-1):
		m = indice_du_min(liste, i)
		liste[i], liste[m] = liste[m], liste[i]





def tri_selection_avec_traces(liste):
	for i in range(len(liste)-1):
		m = indice_du_min(liste, i)
		liste[i], liste[m] = liste[m], liste[i]
		print("{}            {}".format(liste[:i+1],liste[i+1:]))


L = [randint(100,999) for i in range(randint(6,12))]
print("Liste avant le tri : ", L)
print("\nEtapes du tri :" )
tri_selection_avec_traces(L)
print("\nListe après le tri : ", L)

On obtient par exemple : 

Liste avant le tri :  [781, 144, 699, 580, 912, 420, 993, 797, 112, 721, 355]

Etapes du tri :
[112]            [144, 699, 580, 912, 420, 993, 797, 781, 721, 355]
[112, 144]            [699, 580, 912, 420, 993, 797, 781, 721, 355]
[112, 144, 355]            [580, 912, 420, 993, 797, 781, 721, 699]
[112, 144, 355, 420]            [912, 580, 993, 797, 781, 721, 699]
[112, 144, 355, 420, 580]            [912, 993, 797, 781, 721, 699]
[112, 144, 355, 420, 580, 699]            [993, 797, 781, 721, 912]
[112, 144, 355, 420, 580, 699, 721]            [797, 781, 993, 912]
[112, 144, 355, 420, 580, 699, 721, 781]            [797, 993, 912]
[112, 144, 355, 420, 580, 699, 721, 781, 797]            [993, 912]
[112, 144, 355, 420, 580, 699, 721, 781, 797, 912]            [993]

Liste après le tri :  [112, 144, 355, 420, 580, 699, 721, 781, 797, 912, 993]

tri par sélection d'intervalles de temps.

On dispose d'une liste d'intervalles de temps sur une journée. Par exemple, la liste L = [ (1,5), (2,4), (23,24), (5,12) ]. (1,5) est l'intervalle de temps qui commence à 1h et finit à 5h.

On aimerait pouvoir réaliser plusieurs tris d'une telle liste :

  • trier par ordre croissant des heures de début
  • trier par ordre décroissant des heures de début
  • trier par ordre croissant des heures de fin
  • trier par ordre décroissant des heures de fin
  • trier par ordre croissant des durées
  • ...

Programmer une fonction de tri par sélection, prenant en premier paramètre une telle liste et en second paramètre une fonction de comparaison permettant de choisir le critère de tri.

  • un code possible
  • complément python

from random import randint # pour créer une liste au hasard



def heure_fin_croissant(intervalle1, intervalle2) :
	 
	return intervalle1[1] <  intervalle2[1]
	
	
def heure_debut_croissant(intervalle1, intervalle2) :
	# si l'heure de début est la même, 
	# on décide ici de classer par ordre de fin croissant 
	if intervalle1[0] == intervalle2[0] :
		return intervalle1[1] < intervalle2[1]
		 
	return intervalle1[0] < intervalle2[0]
	
	
		 
def heure_debut_decroissant(intervalle1, intervalle2) :
	return intervalle1[0] > intervalle2[0]
	
	
def duree_croissant(intervalle1, intervalle2) :
	return   intervalle1[1] - intervalle1[0] < intervalle2[1] - intervalle2[0]
	 

def indice_du_min(liste, depart, precede):
	"""
	renvoie l'indice d'une valeur minimale 
	parmi liste[depart], liste[depart+1], liste[depart+2], ..., liste[len(liste)-1]
	"""
	valeur_min = liste[depart]
	indice = depart
	for i in range(depart+1, len(liste)):
		if precede(liste[i], valeur_min) :
			valeur_min, indice = liste[i], i
	return indice


def tri_selection(liste, precede ) :
	for i in range(len(liste)-1):
		m = indice_du_min(liste, i, precede)
		liste[i], liste[m] = liste[m], liste[i]
		
		
 

		
def liste_plage() :
	"""
	génère une liste d'intervalles de temps au hasard.
	"""
	L = []
	lg = randint(5,12)
	for i in range(lg) :
		debut = randint(0,23)
		fin = randint(debut+1, 24)
		L.append( (debut, fin) )
	return L 
	
	
		
L = liste_plage()
print("Liste avant le tri : ", L)
tri_selection(L, heure_fin_croissant)
print("\nListe après le tri, heures de fin croissantes : ", L)
tri_selection(L, heure_debut_croissant)
print("\nListe après le tri, heures de début croissantes : ", L)
tri_selection(L, heure_debut_decroissant)
print("\nListe après le tri, heures de début décroissantes : ", L)
tri_selection(L, duree_croissant)
print("\nListe après le tri, durées  croissantes : ", L)

Lorsqu'on définit en Python des objets comme les intervalles de temps ci-dessus, il est possible de définir un nouveau type et de définir comment deux de ces objets seront comparés : 


class Intervalle:
	"""
	Définition des objets "intervalle de temps".
	Ils seront définis par leur début et leur fin.
	"""
	def __init__(self, debut, fin):
		self.debut = debut
		self.fin = fin
	
	def __lt__(self, intervalle):
		""" 
		Pour comparer deux intervalles.
		Ici choix : debuts croissants, 
		et pour des heures de début égales: par fins croissantes.
		"""
		if self.debut == intervalle.debut :
			return self.fin < intervalle.fin
		else :
			return self.debut < intervalle.debut
			
	def __repr__(self):
		"""
		Pour la représentation des objets dans un terminal.
		"""
		return "({},{})".format(self.debut, self.fin)
			
			
	
intervalle1 = Intervalle(3,9)
intervalle2 = Intervalle(4,7)

print( intervalle1 < intervalle2)

intervalle3 = Intervalle(3,8)
print( intervalle1 < intervalle3 )
print( intervalle3 < intervalle1 )

L = [ Intervalle(3,4), Intervalle(1,4), Intervalle(22,24), Intervalle(6,8), Intervalle(23,24),  Intervalle(1,3)]
print("Liste avant le tri : ", L)
L.sort()
print("Liste triée : ", L)

On obtient : 

True
False
True
Liste avant le tri :  [(3,4), (1,4), (22,24), (6,8), (23,24), (1,3)]
Liste triée :  [(1,3), (1,4), (3,4), (6,8), (22,24), (23,24)]

On peut dès lors utiliser la fonction de tri par sélection écrite au départ (sans le second paramètre constitué de la fonction de comparaison : la comparaison est ici définie avec l'objet) : 



class Intervalle:
	"""
	Définition des objets "intervalle de temps".
	Ils seront définis par leur début et leur fin.
	"""
	def __init__(self, debut, fin):
		self.debut = debut
		self.fin = fin
	
	def __lt__(self, intervalle):
		""" 
		Pour comparer deux intervalles.
		Ici choix : debuts croissants, 
		et pour des heures de début égales: par fins croissantes.
		"""
		if self.debut == intervalle.debut :
			return self.fin < intervalle.fin
		else :
			return self.debut < intervalle.debut
			
	def __repr__(self):
		"""
		Pour la représentation des objets dans un terminal.
		"""
		return "({},{})".format(self.debut, self.fin)
			



def indice_du_min(liste, depart):
	"""
	renvoie l'indice d'une valeur minimale
	parmi liste[depart], liste[depart+1], liste[depart+2], ..., liste[len(liste)-1]
	"""
	valeur_min = liste[depart]
	indice = depart
	for i in range(depart+1, len(liste)):
		if liste[i] < valeur_min :
			valeur_min, indice = liste[i], i
	return indice


def tri_selection(liste) :
	for i in range(len(liste)-1):
		m = indice_du_min(liste, i)
		liste[i], liste[m] = liste[m], liste[i]
			
	
 

L = [ Intervalle(3,4), Intervalle(1,4), Intervalle(22,24), Intervalle(6,8), Intervalle(23,24),  Intervalle(1,3)]
print("Liste avant le tri : ", L)
tri_selection(L)
print("Liste triée : ", L)