P5.1b les algorithmes de constructions de liste

On veut retourner une liste (c'est à dire ranger ses éléments dans l'ordre inverse) et on va procéder par ajouter successifs (il existe d'autres façons de le faire).
L'algorithme est assez simple :

fonction retourner(lst) :
lstReverse = [ ]
tant que lst non vide :
retirer le dernier elem de lst et l'ajouter à la fin de lstReverse
fin de pour
renvoyer lstReverse

Coder ceci en python ne pose pas de grosse difficulté, mais il faut se souvenir de la méthode pop et de son usage….
Voici un code qui va te servir d'exemple pour l'exercice.

Rappel :
lst = [1,2,3]
a = lst.pop()
-> a=3 et maintenant lst=[1,2]
lst.pop() retire le dernier élément de la liste lst et renvoie sa valeur.

pyBox slug='5.1_reversePOP' solver="def reversePOP(lst: list ) -> list : lstR=[] while len(lst) > 0: e=lst.pop() lstR.append(e) return lstR lst=[3,1,6,7,2] print(reversePOP(lst)) " defaultcode="def reversePOP(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reversePOP(lst)) " taboo="insert" title='reverse avec pop' ] [/pyBox]

Au lieu de append, on pourrait aussi utiliser une concaténation de liste : lstR = lstR + [val] donnera le même résultat, essaye les deux façons.
(attention : en réalité ces deux façon de procéder ne sont pas équivalentes. Elle donnent le même résultat et pour cette année nous n'entreront pas dans les détails sr la différence de traitement entre les deux)

On pourrait même ne rien ajouter et ne rien concaténer :

def reversePOP(lst: list ) -> list :
    lstR=[0] * len(lst) # initialise une liste avec len(lst) 0
    idx=0
    while len(lst) > 0:
        e=lst.pop()
        lstR[idx]=e
        idx+=1
    return lstR

Et là encore, le résultat est le même mais les opérations réalisées ne sont pas les même en réalités. Et ici aussi nous n'entreront pas cette année dans les détails.

Toutefois nous aurions pu écrire aussi bien cet algorithme :

onction retourner(lst) :
lstReverse = [ ]
tant que lst non vide :
retirer le premier elem de lst et l'ajouter au début de lstReverse
fin de pour
renvoyer lstReverse

Tu pourras coder ce second algorithme en utilisant lst.pop(0) qui retire l'élément d'indice 0 et lstR.insert(0,val) qui insère val en tête de liste.

On pourrait aussi utiliser une concaténation de liste : lstR = [val] + lstR donnera le même résultat, essaye les deux façons, et surtout remarque bien :

ajouter en tête : lst.insert(0,val) ou lst=[val] + lst
ajouter en queue : lst.append(val) ou lst=lst+[val]
retirer en tête : val = lst.pop(0)
retirer en queue :val = lst.pop()

Rappel :
lst = [1,2,3]
lst.insert(0,7)
-> Maintenant lst vaut [7,1,2,3]

Coding Exercise: reverse avec insert

You need to create an account and log in to ask a question.

def reverseInsert(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reverseInsert(lst))

More actions... Reset code to default Help

Complexité

Pouvez vous estimer la complexité de ces différents codes de retournement ? Sont ils tous équivalent ?

Vous aller programmer ici une fonction tri(lst) qui va trier une liste. L'algorithme utilisé, que nous reverrons plus tard dans une autre forme, est le suivant :

fonction triInsertion(lst) :
  listTriee=[]
  Tant que longueur(lst) > 0 :
    rechercher l'indice du min dans lst
    retirer cet élément (avec pop) et l'ajouter (en queue) dans listeTrie
  fin de tant que
  renvoyer listeTriee
(la fonction idxMin(list) est disponible dans cet exercice)

Coding Exercise

You need to create an account and log in to ask a question.

def tri(lst: list ) -> list : ''' documentez ''' # votre code ici lst=[3,1,6,7,2] print(tri(lst))

More actions... Reset code to default Help

Dans ce code, que vous venez de faire, on n'a pas vraiment de curseurs (il y en a cependant un, caché dans la fonction idxMin que vous avez utilisé), d'accumulateur, ou de compteur. En effet ici on ne compte rien, on ne somme rien, et on ne localise rien.

L'ajout successif d'élément dans une liste est un autre outil indispensable que vous serez souvent amenés à utiliser.

Complexité

Estimons la complexité de cet algorithme expérimentalement avec time().

Example

def tri(lst: list ) -> list : lstTriee=[] while len(lst) > 0: i=idxMin(lst) e=lst.pop(i) lstTriee.append(e) return lstTriee def idxMin(lst : list) -> int: idxMin=0 for i in range(1,len(lst)) : if lst[i] < lst[idxMin]: idxMin=i return idxMin from time import time tref=1 for N in (10,20,40,80,160,320,640,1280,2560) : lst=[i for i in range(N,0,-1)] debut=time() tri(lst) fin=time() print('N=',N,'dt= ',fin-debut,' x ',(fin-debut)/tref) tref=fin-debut

En raison de limitations sur ce site, il n'est pas possible de travailler sur de très grandes listes. Néanmoins, ici, on a pris une séries de valeurs de N allant de 10 à 2560. A chaque fois on multiplie N par 2. Le temps de calcul évolue d'abord linéairement pour les petites valeurs de N mais rapidement on voit que quand N est multiplié par 2, le temps est multiplié par 4 (2² !)
La complexité semble donc plutôt proportionnelle à N² dans cet exemple.

Combien de fois est exécutée la boucle while ?
Combien d'opération sont executées dans cette boucle while ?

La réponse est que la boucle while est exécutée N fois, mais dans la boucle, on appelle idxMin. idxMin a une complexité en O(N), mais comme la liste lst est raccourcie au fur et a mesure, c'est un peu compliqué….

• Au premier tour, idxMin cherche dans une liste de longueur N
• A second tour dans une liste de longueur N-1
• Au troisième tour, dans une liste de longueur N-2
• etc… jusqu'au dernier tour, ou il ne reste qu'un élément.

si le temps de idxMin est N, alors le temps de tout les appels est :
1 + 2 + … + N = N(N+1)/2 = N² /2 + N/2

pour de grandes valeurs de N, N² >> N, la complexité sera proportionnelle à N². On parle ici de complexité quadratique que l'on note O(N²)