1) Introduction
Comment trier dans l’ordre croissant un tableau d’entier ?
2) Tri par insertion
Les animations du lien ci-dessous doivent vous permettre de comprendre cet algorithme de tri.
https://interstices.info/les-algorithmes-de-tri/
Découpez 5 petites cartes et écrire les entiers du tableau qui va nous servir d’exemple.
Vérifiez que vous êtes capable de trier le tableau avec l’algorithme de tri par insertion.
ci-dessous l’implémentation de l’algorithme en python
exécuter le programme pas à pas dans python tutor pour vous aider à comprendre l’algorithme.
Vous devez être capable d’exécuter le programme sur une feuille de papier sans python tutor
2) Tri par sélection
Effectuez le même travail sur le tri par sélection
https://interstices.info/les-algorithmes-de-tri/
4) Comparaison des tris
La méthode sort() permet de trier un tableau :
On peut générer un tableau de n entiers aléatoires ,effectuer un tri et mesurer le temps d’exécution.
Avec 10 entiers le temps est si petit qu’il n’est pas mesurable.
à vous de tester avec plus d’entiers en évitant d’afficher les tableaux.
pour n=1000 ,10000,10000
comparez les deux tris étudiés avec le tri effectué par la méthode sort.
corrigé:
import time
import random
n=100000
tab=[]
# On génère un tableau d'entiers aléatoires
for i in range(n):
tab.append(random.randint(0,n))
# On copie la liste tab générée pour trier la même liste(le tri modifie la liste)
tab1=list(tab)
tab2=list(tab)
# Tri de tab avec la méthode intégrée à python
debut=time.time()
tab.sort()
duree=time.time()-debut
print('durée sort() pour n=',n," : " , duree ,'s')
# Tri selection d'une copie de tab
debut=time.time()
tri_selection(tab1)
duree=time.time()-debut
print('durée tri_selection() pour n=',n," : " , duree ,'s')
# Tri insertion d'une copie de tab
debut=time.time()
tri_insertion(tab2)
duree=time.time()-debut
print('durée tri_insertion() pour n=',n," : " , duree ,'s')
