Chapitre : Tri insertion V.S tri selection



On complétera au fur et à mesure un fichier Thonny. (insertVSselect.py)

En cas de probleme pour l'obtention des graphique, avec Thonny, vous pouvez utiliser Trinket ( LIEN )

TRI PAR SELECTION

Voici l'algorithme du tri par sélection : 


	
def permuter(L,i,j):
    """
    permute les elements d'indice i et j de L
    exemple :
    >>>permuter([12,7,8,45],1,2)
    [12,8,7,45]
    """
    tmp=L[i]
    L[i]= L[j]
    L[j]=tmp
    return L
	
def tri_select(L):
    n = len(L)
    # la tranche l[0:1] est triée
    for i in range(n - 1):
        for j in range(i+1,n):
            if L[j] < L[i] :
                permuter(L, i, j)
    return L


Tester le tri par selection avec les listes : 


L1=[12,48,5,1,0,9,87]
L2=[k for k in range(15,0,-1)]
L3=[k for  k in range(0,15)]
print("L1=", L1)
print("L2=",L2)
print("L3=",L3)

Ecrire l'affichage obtenu avec Trinket ou Thonny :



Ajouter le code ci-desous au début de votre fichier Thonny

import random  #gestion de l'aleatoire
import time # gestion du temps
import matplotlib.pyplot as plt # gestion des graphiques

A l'aide de Thonny, indiquer le rôle de chacune des lignes ci-dessous : 

time1=time.time() 
print('Bonjour')
L=[k for  k in range(5000)]
random.shuffle(L)
tri_select(L)
time2=time.time()
print(time2-time1)

Ecrire vos réponses : 

time1=time.time()           #.....
print('Bonjour')            #.....
L=[k for  k in range(5000)] #.....
random.shuffle(L)           #.....
select_sort(L)              #.....
time2=time.time()           #.....
print(time2-time1)          #.....


  1. Avec le tri par selection, combien de temps faut-il à python pour trier une liste desordonnée (aléatoire) de 10000 valeurs ?
  2. Avec le tri par selection, combien de temps faut-il à python pour trier une liste ordonnée (croissant) de 10000 valeurs ?
  3. Avec le tri par selection, combien de temps faut-il à python pour trier une liste ordonnée ( décroissant) de 10000 valeurs ?
  4. Tester puis expliquer ce que fait la fonction ci-dessous ? 
    5. def temps_tri_selectionV1():
    TEMPS=[] #liste vide
    for i in range(2,300):
        L=[k for  k in range(0,i)]
        random.shuffle(L)        
        time1=time.time() 
        tri_select(L)
        time2=time.time()
        T=time2-time1
        TEMPS.append(T)
    return TEMPS



Les 3 lignes ci-dessous permettent de visualiser les temps sous la forme d'un graphique :


plt.plot(temps_tri_selectionV1(), label="aleatoire")
plt.legend()
plt.show()
  1. Tester le code ci-dessus.
  2. Sauvegarder le graphique.
  3. Afficher ci-dessous le graphique obtenu.


  1. Réecrire la fonction temps_tri_selectionV1 ( que l'on nomera temps_tri_selectionV2 ) afin d'obteniur un graphique dans le cas de tri de listes ordonées (décroissante).
  2. Afficher ci-dessous le graphe obtenue.

  1. Réecrire la fonction temps_tri_selectionV1 ( que l'on nomera temps_tri_selectionV3 ) afin d'obteniur un graphique dans le cas de tri de listes ordonées (croissante).
  2. Afficher ci-dessous le graphe obtenu.

  1. Le code ci-dessous permet de mettre plusieurs courbes sur le même graphique.
    2. plt.plot(temps_tri_selectionV1(), label="tri select aléa")
plt.plot(temps_tri_selectionV2(), label="tri select décroissant")
plt.plot(temps_tri_selectionV3(), label="tri select croissant")
plt.legend()
plt.show()
  2. Afficher ci-dessous le graphe obtenu.

TRI PAR INSERTION ET COMPARAISON



Le code ci-dessous, vous permet de trier par INSERTION les 3 types de liste (aléatoire, croissante, décroissante)

def tri_insert(L):
    n=len(L)
    for i in range (1,n):
        k=i
        while k>0 and L[k] < L[k-1] :
            permuter(L,k,k-1)
            k=k-1
    return L

Cas aléatoire

En vous aidant du travail précédent, générer un graphique qui compare le temps mis (par insertion et par selection ) pour trier une liste aléatoire.

On ecrira la fonction : temps_tri_insertV1()



Le pire des cas !

En vous aidant du travail précédent, générer un graphique qui compare le temps mis (par insertion et par selection ) pour trier une liste rangés dans l'odre décroissant.

On ecrira la fonction : temps_tri_insertV2()



Le meilleur des cas !

En vous aidant du travail précédent, générer un graphique qui compare le temps mis (par insertion et par selection ) pour trier une liste déja triée.

On ecrira la fonction : temps_tri_insertV3()



Faire une analyse des trois graphiques obtenus.

.