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 lstReverseCoder 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 :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]
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.
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 :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.
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
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 lstReverseTu 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]
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)
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().
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²)
