NUMERIQUE ET SCIENCES INFORMATIQUES

N.B. Niveau : Terminale Générale, enseignement de spécialité NSI (Numérique et Sciences Informatiques)

 
  1. Programmation orientée objet
  2. Récursivité
  3. Base de données et langage SQL
  4. Les listes chainées
  5. Piles et Files
  6. Les dictionnaires
  7. Protocoles de routage
  8. Les arbres
  9. Sécurisation des données
  10. Diviser pour régner
  11. Les processus
  12. Les systèmes sur puce
  13. Recherche textuelle
  14. Les Graphes
  15. L'intelligence artificielle
  16. Epreuves pratiques et écrites du Bac
  17. Le grand oral
 
  1. Algorithmes de référence de première
  2. Mise au point des programmes
  3. Algorithme de recherche dichotomique
  4. Algorithmes de tri par insertion
  5. Fractales récursives
  6. Algorithmes de tri par sélection
  7. Base de données et langage SQL
  8. Modularité
 
  1. Devoir maison n°1
  2. Les 48 sujets de l'épreuve pratique 2024
  3. Les 45 sujets de l'épreuve pratique 2023
 

D
É
C
O
N
N
E
C
T
É

Algorithmes de référence de première

1 - Principe du tri par sélection

À savoir

Le tri par sélection d'un tableau consiste à

  • chercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 0 du tableau,
  • chercher le deuxième plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 du tableau,
  • chercher le troisième plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 du tableau,
  • continuer de cette façon jusqu'à atteindre la fin du tableau. (Cela prend n - 1 étapes, où n est la taille du tableau.)

Ainsi, après k étapes de tri, les k premiers éléments du tableau (donc les éléments d'indice 0 à k - 1) sont triés. On cherche le plus petit des éléments restants (les éléments restants étant les éléments d'indices supérieurs ou égaux à k), et on l'échange avec l'élément d'indice k du tableau.

Exemple (à faire avec le professeur) :

Si l'on veut trier le tableau [3, 10, 7, 1, 5], on effectue les étapes décrites dans le tableau ci-dessous :

ÉtapeTableau au départIndice du premier élément non triéMinimum à partir de l'indiceIndice du minimumTableau après échange
1
2
3
4

    

Exercice 1 :

Compléter le tableau ci-dessous avec les différentes étapes du tri par sélection, si le tableau à trier est [100, 3, 0, 7, 10, 80] :

ÉtapeTableau au départIndice du premier élément non triéMinimum à partir de l'indiceIndice du minimumTableau après échange
1
2
3
4
5

    

2 - Programmation du tri par sélection en Python

2.1 - Fonction de sélection

Lorsqu'on réalise un tri par sélection, après k étapes, les éléments d'indice 0 à k - 1 sont triés. Notons m l'indice du plus petit des éléments non triés (ceux dont l'indice est supérieur ou égal à k). L'étape suivante du tri consiste à échanger l'élément d'indice k et l'élément d'indice m. Bien sûr, cela nécessite de connaître la valeur de m. On peut l'obtenir grâce à une fonction.

Exercice 2 :

a) Écrire en Python une fonction selection_min qui :

  • prend en paramètres un tableau tab et un indice k,
  • retourne l'indice du plus petit élément de tab à partir de l'indice k.

Par exemple selection_min([1,3,7,10,5], 2) devra retourner l'indice du plus petit élément à partir de l'indice 2, c'est-à-dire 4 (l'indice de l'élément 5).

b) Tester la fonction selection_min dans plusieurs cas, sans oublier les cas limites.

     



			

			
						

						


			
	
			
			

		
	
	

	
	
2.2 Fonction de tri par sélection


		

		
Considérons un tableau tab et notons n sa longueur. Pour réaliser un tri par sélection, 
			il faut initialiser une variable k à 0 puis répéter n - 1 fois :

		
  • noter m l'indice du plus petit élément du tableau à partir de l'indice k,
    • 
			
  • échanger l'élément d'indice k et l'élément d'indice m du tableau,
    • 
			
  • augmenter de 1 la valeur de k.
    • 
		
    Exercice 3.
    		
		
    a) Écrire en Python une fonction tri_selection qui :
    
		
    • prend en paramètre un tableau tab
      • 
			
    • retourne ce même tableau trié par ordre croissant grâce au tri par sélection.
      • 
		
    
		
    Par exemple tri_selection([3, 1, 0, 5, 8]) devra retourner [0, 1, 3, 5, 8]
    
		
    Attention : La fonction tri_selection devra faire appel à la fonction selection_min.
    
		
    b) Tester la fonction tri_selection, en pensant à réaliser plusieurs tests et à tester les cas limites.
    	
		
    		
		
		
    

		  

		
    
		    
    
		
    

		
    
		
					
    
					


		
    
	
    

	
		
3 Exercice 4 : variantes

		
		

			
a) Écrire en Python une fonction récursive tri_selection_rec qui :

			
  • prend en paramètre un tableau tab et un entier debut,
    • 
				
  • retourne ce même tableau trié par ordre croissant à partir de l'indice debut grâce au tri par sélection.
    • 
			

		
Par exemple tri_selection_rec([3, 1, 8, 5, 18], 2) devra retourner [3, 1, 5, 8, 18]

		
La fonction tri_selection_rec devra faire appel à la fonction selection_min.	

		
		

			
			


			  

			
 
				    

			


			

			
						

						


			
			
		
		
		
b) Regrouper les fonctions selection_min et tri_selection_rec en une seule fonction de tri 
		que l'on nommera tri_selection2.

			
		

			
			


			  

			
 
				    

			


			

			
						

						


			
			
		
				
				
	
	

	

	

	











































































Fond :   
Texte :    
Tables :   
Thème Python: