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 insertion

À savoir

Le tri par insertion est le tri du jeu de cartes : on met les cartes dans l'ordre au fur et à mesure où on les reçoit.
Pour effectuer un tri par insertion, on peut utiliser deux listes :
une liste contenant les éléments à trier, et une liste qui contiendra les éléments déjà triés.
Cette seconde liste est initialisée à la liste vide.
Puis, on insère un par un les éléments de la liste à trier (en partant de la fin) à leur place dans la liste d'éléments déjà triés.

Exemple (à faire avec le professeur) :

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

ÉtapeListe à trierÉlément à insérerListe triée après insertion
Initialisation[3, 1, 7, 2]-[ ]
1
2
3
4

    

Exercice 1 :

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

ÉtapeListe à trierÉlément à insérerListe triée après insertion
Initialisation[100, 3, 0, 7, 10]-[ ]
1
2
3
4
5

    

À savoir

Plutôt que de manier deux listes, on peut utiliser un tableau, de taille constante, constitué :

  • au début, des éléments à trier,
  • à la fin, des éléments triés.
    • à trierdéjà trié

Pour réaliser le tri, on ne fait alors qu'échanger la place des éléments dans le tableau. C'est ce que l'on appelle un tri en place.

Exemple (à faire avec le professeur) :

Trions avec cette méthode le tableau [4, 8, 10, 2, 5].

ÉtapeListe à trierPartie triéeTableau complet
Initialisation[4, 8, 10, 2, 5][][4, 8, 10, 2, 5]
1
2
3
4
5

    

Exercice 2 :

Faire de même que l'exemple ci-dessus, pour le tableau [9, 1, 42, 20, 5]

ÉtapeListe à trierPartie triéeTableau complet
Initialisation
1
2
3
4
5

    

2 - Programmation du tri par insertion en Python

2.1 - Fonction insertion

À savoir

Supposons que l'on dispose d'un tableau constitué

  • d'éléments à trier jusqu'à un indice i,
  • suivis d'éléments triés à partir de l'indice i+1.

Pour réaliser une itération de l'algorithme de tri par insertion, on désire insérer le dernier élément de la partie à trier, c'est-à-dire celui d'indice i, à la bonne place dans la partie triée.

Pour cela :

Exemple (à faire avec le professeur) :

Le tableau [40, 250, 1, 16, 7, 8, 12, 20, 300] contient une partie non triée de l'indice 0 jusqu'à l'indice i=3, et une partie triée de l'indice 4 jusqu'à la fin du tableau.

Pour réaliser une itération du tri par insertion, il faut insérer l'élément d'indice 3, donc 16, à la bonne place dans la partie trié du tableau ([7, 8, 12, 20, 300]). On procède comme suit :

Étapejtest : tab[j] > tab[j+1]résultat du testtableau après échange
1
2
3
4

    

Exercice 3 :

a) Écrire en Python une fonction insertion qui :

  • prend en paramètres :
    • un entier, noté i,
    • et un tableau d'entiers, noté tab, et tel que à partir de l'indice i+1, les éléments de tab sont triés dans l'ordre croisant,
  • insère l'élément d'indice i à la bonne place parmi les éléments suivants, c'est-à-dire déplace l'élément d'indice i de manière à ce que tab soir trié à partir de l'indice i,
  • retourne le tableau obtenu.

    • Par exemple insertion(3, [40, 250, 1, 16, 7, 8, 12, 20, 300]) devra retourner : [40, 250, 1, 7, 8, 12, 16, 20, 300] (voir exemple ci-dessus).

    Attention, la fonction insertion ne devra pas avoir d'effets de bord.

b) Tester la fonction insertion sur plusieurs exemples.

Penser à tester la fonction insertion dans des cas limites : cas où la partie triée est vide, cas où l'élément est à insérer tout au début de la partie triée, cas où l'élément est à insérer tout à la fin du tableau.

     



			

			
						

						


			
	
			

		

	
	
	
		
2.2 Fonction de tri par insertion

		
Exercice 4.

		

		

		
Dans cet exercice, nous allons utiliser la fonction précédente pour concevoir une fonction de tri par insertion.

		
a) Écrire en Python une fonction tri_insertion qui :

		

		
  • prend en paramètre un tableau
    • 
			
  • et retourne ce même tableau trié par ordre croissant grâce au tri par insertion.
    • 
		

		
Par exemple tri_insertion([3, 1, 0, 5, 8]) devra retourner [0, 1, 3, 5, 8]

		
Attention : La fonction tri_insertion devra faire appel à la fonction insertion et ne devra pas avoir d'effets de bord.

		

		
b) Tester la fonction tri_insertion, en pensant à réaliser plusieurs tests et à tester les cas limites.
	
		
		
		
		


		  

		

		    

		


		

		
					

					


		

	


	
	
Complexité :

	

		
Propriété

		

			
Pour tout entier positif n, on a :

			
 
			

		

		
Nous allons déterminer la complexité en nombre de comparaisons dans le pire cas de la fonction
			tri_insertion, en fonction de la longueur n du tableau.

		
  •  Considérons un appel à la fonction insertion où la longueur de la partie triée est k.
    
				Dans le pire des cas, l'élément à insérer d'insère à la fin de la partie triée : 
    
				on fait une comparaison par élément de la partie triée. Si la longueur de la partie triée est k, on fait
				donc k comparaisons dans le pire des cas.
    • 
		
  • Au début, la partie triée est vide, et on y ajoute un élément à chaque itération. À la k-ième
			itération de la boucle de la fonction tri_insertion, la taille de la partie triée au moment
			de l'appel à la fonction insertion est donc k - 1.
    • 
		
  • Notons n la taille de la liste à trier. D'après les deux points précédents, la complexité en
			nombre de comparaisons dans le pire des cas de la fonction tri_insertion est : 
    
			 
		
    • 
		

		
C'est une complexité quadratique (à savoir)

	

		
		
Exercice 5 (Variantes).

		

			
a) Réécrire une fonction de tri par insertion, similaire à celle de l'exercice 4 mais sans avoir recours
				à une fonction annexe. Pour cela, on combinera les fonctions insertion et tri_insertion des
				exercices 3 et 4 en une seule fonction, que l'on nommera tri_insertion2.

		

			
			


			  

			
 
				    

			


			

			
						

						


			
			
		
		
				
				
				
			
b) Modifier la fonction tri_insertion pour qu'elle trie un tableau dans l'ordre décroissant. Vous la nommerez tri_insertion3

			
		

			
			
			


			  

			

			      

			


			

			
						

						


			

			

		

	


	

	

	











































































Fond :   
Texte :    
Tables :   
Thème Python: