Listes - Exercices

NoteFonctionalitées avancées des listes

Les exercices ci-dessous présentent des fonctionnalités avancées des listes en Python. Afin de bien les comprendre, vous devrez concevoir et analyser les algorithmes qui se cachent derrière ces fonctionnalités en utilisant uniquement les notions fondamentales et les fonctions de base des listes vues jusqu’à présent.

1 Indexation négative des éléments de la liste (negative indexing)

Python permet d’accéder aux éléments d’une liste en utilisant des index négatifs, ce qui permet de référencer les éléments à partir de la fin de la liste. Par exemple, l’index \(-1\) fait référence au dernier élément de la liste, l’index \(-2\) fait référence à l’avant-dernier élément, et ainsi de suite.

1.1 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
nbItems = len(items)
print("items:", items, "size:", nbItems)
firstItem = items[0]
print("firstItem:", firstItem)
lastItem = items[-1] # équivalent à items[len(items) - 1]
print("lastItem:", lastItem)
beforeLastItem = items[-2] # équivalent à items[len(items) - 2]
print("beforeLastItem:", beforeLastItem)
# default_end

1.2 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(items, index, direction):
    result = None
    if direction == "forward":
        result = items[index]
    if direction == "backward":
        result = items[-index]
    return result
# default_end
# test_start
print(mystere([1, 2, 3, 4], 0, "forward"))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4], 1, "backward"))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4], 3, "forward"))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4], 4, "backward"))
# test_end
# default_start
def mystere(items, index, direction):   # items = [1, 2, 3, 4], index = 1, direction = "backward"
    result = None                       # result = None
    if direction == "forward":          # "backward" == "forward" ? False
        result = items[index]           # 
    if direction == "backward":         # "backward" == "backward" ? True
        result = items[-index]          # result = items[-1] -> result = 4
    return result                       # return 4
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’indexation négative des listes en utilisant uniquement les fondamentaux et les fonctions de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myGet\) qui prend en entrée une liste \(items\) et un index \(index\), et qui retourne l’élément de la liste correspondant à cet index. L’index peut être positif ou négatif.

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myGet(items, index):
    return None
# default_end
# test_start
print(myGet([1, 2, 3, 4, 5], 0))
print("C683AKRMaR")
print(myGet([1, 2, 3, 4, 5], 3))
print("C683AKRMaR")
print(myGet([1, 2, 3, 4, 5], -1))
print("C683AKRMaR")
print(myGet([1, 2, 3, 4, 5], -3))
# test_end
# solution_start
def myGet(items, index):
    item = None
    if index >= 0:
        item = items[index]
    else:
        item = items[len(items) + index]
    return item
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’indexation négative des éléments d’une liste ?

# default_start
def get(items, index):
    item = None                             # 1 affectation
    if index >= 0:                          # 1 comparaison
        item = items[index]                 # 1 affectation + 1 accès
    else:                                   # 1 comparaison
        item = items[len(items) + index]    # 1 affectation + 1 accès + 1 addition
    return item                             # 1 retour
# T(n) = 1 + max(1 + 2, 1 + 3) + 1 
#      = 6
#      = O(1)
# default_end

2 Parcourir une liste par élement avec une boucle (for loop)

Python permet de parcourir les éléments d’une liste directement à l’aide d’une boucle \(for\), sans avoir besoin de gérer les index.

2.1 Syntaxe

# exercice: show
# default_start
# Parcourir une liste avec une boucle for
for item in listName:
    # faire quelque chose avec item
# default_end

2.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
for item in items:
    print("item:", item)
# default_end

2.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(values, threshold):
    count = 0
    for value in values:
        if value > threshold:
            count = count + 1
    return count
# default_end
# test_start
print(mystere([1, 2, 3, 4, 5], 3))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 5))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 0))
# test_end
# default_start
def mystere(values, threshold):     # values = [1, 2, 3, 4, 5], threshold = 3
    count = 0                       # result = 0
    for value in values:            # value = 1       value = 2       value = 3       value = 4             value = 5
        if value > threshold:       # 1 > 3 ? False   2 > 3 ? False   3 > 3 ? False   4 > 3 ? True          5 > 3 ? True
            count = count + 1       #                                                 result = 0 + 1 = 1    result = 1 + 1 = 2
    return count                    # return 2
print(mystere([1, 2, 3, 4, 5], 3))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la boucle \(for\) en utilisant uniquement les fondamentaux et les fonctions de base des listes que nous avons vus jusqu’à présent.

Récrire la fonction mystere ci-dessus mais en utilisant une boucle \(while\) au lieu d’une boucle \(for\).

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def mystere(values, threshold):
     return None
# default_end
# test_start
print(mystere([1, 2, 3, 4, 5], 3))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 5))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 0))
# test_end
# solution_start
def mystere(values, threshold):
    count = 0
    i = 0
    while i < len(values):
        value = values[i]
        if value > threshold:
            count = count + 1
        i = i + 1
    return count
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la fonction mystere ci-dessus ?

# default_start
def mystere(values, threshold):                
    count = 0                   # 1 affectation
    i = 0                       # 1 affectation
    # len(values) itérations
    while i < len(values):      # 1 comparaison + 1 longueur
        value = values[i]       # 1 affectation + 1 accès
        if value > threshold:   # 1 comparaison
            count = count + 1   # 1 affectation + 1 addition
        i = i + 1               # 1 affectation + 1 addition
    return count                # 1 retour
# n = len(values)
# T(n) = 2 + n * (2 + 2 + 1 + 2 + 2) + 1
#      = 9n + 3
#      = O(n)
# default_end

3 Parcourir une liste par index avec une boucle (range() function)

Python permet également de parcourir les éléments d’une liste à l’aide d’une boucle \(for\) en utilisant la fonction \(range()\) pour générer les index des éléments de la liste.

3.1 Syntaxe

# exercice: show
# default_start
# Parcourir une liste avec une boucle for et la fonction range()
for index in range(start, end, step):
    item = listName[index]
    # faire quelque chose avec item
# default_end

3.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
for index in range(0, len(items), 1):
    item = items[index]
    print("index:", index, "item:", item)
# default_end

3.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(values, start, end, step):
    result = 0
    for index in range(start, end, step):
            result = result + values[index]
    return result
# default_end
# test_start
print(mystere([1, 2, 3, 4, 5], 0, 5, 1))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 4, 1, -1))
print("C683AKRMaR")
print(mystere([1, 2, 3, 4, 5], 1, 5, 2))
# test_end
# default_start
def mystere(values, start, end):            # values = [1, 2, 3, 4, 5], start = 1, end = 5, step = 2
    result = 0                              # index = 1
                                            # range(1, 5, 2) -> [1, 3]
    for index in range(start, end, 1):      # index = 1                      index = 3
            result = result + values[index] # result = 0 + values[1] = 2     result = 2 + values[3] = 6
    return result                           # return 6
print(mystere([1, 2, 3, 4, 5], 1, 5, 2))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la fonction \(range()\) en utilisant uniquement les fondamentaux et les fonctions de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myRange\) qui prend en entrée trois paramètres \(start\), \(end\) et \(step\), et qui retourne une liste contenant les entiers de \(start\) (inclus) à \(end\) (exclus) avec un pas de \(step\).

  • Si \(step\) est égal à zéro, la fonction doit retourner \(None\)
  • Si \(start\) est inférieur à \(end\) et \(step\) est négatif, la fonction doit retourner \(None\).
  • Si \(start\) est supérieur à \(end\) et \(step\) est positif, la fonction doit retourner \(None\).
# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myRange(start, end, step):
    return None
# default_end
# test_start
print(myRange(0, 5, 1))
print("C683AKRMaR")
print(myRange(10, 0, -2))
print("C683AKRMaR")
print(myRange(3, 9, 3))
print("C683AKRMaR")
print(myRange(3, 9, 0))
print("C683AKRMaR")
print(myRange(9, 3, 1))

# test_end
# solution_start
def myRange(start, end, step):
    result = None
    if step != 0:
        if start < end and step > 0:
            size = (end - start) // step
            result = [0] * size
            i = 0
            while i < size:
                result[i] = start + i * step
                i = i + 1
        if start > end and step < 0:
            size = (start - end) // (-step)
            result = [0] * size
            i = 0
            while i < size:
                result[i] = start + i * step
                i = i + 1
    return result
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la fonction range() ?

# default_start
def myRange(start, end, step):
    result = None                               # 1 affectation
    if step != 0:                               # 1 comparaison
        if start < end and step > 0:            # 1 comparaison + 1 comparaison
            size = (end - start) // step        # 1 affectation + 1 soustraction + 1 division
            result = [0] * size                 # 1 affectation + O(size) créations d'éléments
            i = 0                               # 1 affectation
            # size itérations
            while i < size:                     # 1 comparaison
                result[i] = start + i * step    # 1 accès + 1 affectation + 1 addition + 1 multiplication
                i = i + 1                       # 1 affectation + 1 addition
        
        if start > end and step < 0:            # 1 comparaison + 1 comparaison
            size = (start - end) // (-step)     # 1 affectation + 1 soustraction + 1 division
            result = [0] * size                 # 1 affectation + O(size) créations d'éléments
            i = 0                               # 1 affectation
            # size itérations
            while i < size:                     # 1 comparaison
                result[i] = start + i * step    # 1 accès + 1 affectation + 1 addition + 1 multiplication
                i = i + 1                       # 1 affectation + 1 addition
    return result                               # 1 retour
# n = size = abs(end - start) // abs(step)
# T(n) = 1 + 1 + max(2 + 3 + O(n) + 1 + 1 + n * (1 + 4 + 2), 2 + 2 + 3 + 1 + O(n) + 1 + n * (1 + 4 + 2)) + 1
#      = 2 + max(5 + O(n) + 2 + 7n, 8 + O(n) + 1 + 7n) + 1
#      = 2 + max(8n + 7, 8n + 9) + 1
#      = 8n + 9 + 3
#      = O(n)
# default_end

4 Vérifier si un élément est présent dans une liste (in operator)

Python permet de vérifier si un élément est présent dans une liste à l’aide de l’opérateur \(in\). L’opérateur \(in\) retourne \(True\) si l’élément est présent dans la liste, et \(False\) sinon.

4.1 Syntaxe

# exercice: show
# default_start
# Vérifier si un élément est présent dans une liste
isPresent = item in listName # retourne True si item est présent dans listName, et False sinon
# default_end

4.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
isPresent = 2 in items
print("isPresent:", isPresent)
isPresent = 4 in items
print("isPresent:", isPresent)
# default_end

4.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(items1, items2, item, mode):
    result = False
    if mode == "any":
        result = item in items1 or item in items2
    if mode == "all":
        result = item in items1 and item in items2
    return result
# default_end
# test_start
print(mystere([1, 2, 3], [4, 5, 6], 2, "any"))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4, 5, 6], 2, "all"))
print("C683AKRMaR")
print(mystere([1, 2, 3], [2, 3, 4], 2, "any"))
print("C683AKRMaR")
print(mystere([1, 2, 3], [2, 3, 4], 2, "all")) 
# test_end
# default_start
def mystere(list1, list2, item, mode):              # list1 = [1, 2, 3], list2 = [4, 5, 6], item = 2, mode = "any"
    result = False                                  # result = False
    if mode == "any":                               # "any" == "any" -> True
        result = item in list1 or item in list2     # result = 2 in [1, 2, 3] or 2 in [4, 5, 6] -> True or False -> True
    if mode == "all":                               # "any" == "all" -> False
        result = item in list1 and item in list2    # result = 2 in [1, 2, 3] and 2 in [4, 5, 6] -> True and False -> False
    return result                                   # return True
print(mystere([1, 2, 3], [4, 5, 6], 2, "any"))
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’opérateur de listes \(in\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myIn(items, item)\) qui prend en entrée une liste \(items\) et un élément \(item\), et qui retourne \(True\) si l’élément est présent dans la liste, et \(False\) sinon.

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myIn(items, item):
    return None
# default_end
# test_start
print(myIn([1, 2, 3], 2))
print("C683AKRMaR")
print(myIn([1, 2, 3], 4))
print("C683AKRMaR")
print(myIn([], 1))
# test_end
# solution_start
def myIn(items, item):
    found = False
    i = 0
    while not found and i < len(items):
        if items[i] == item:
            found = True
        i = i + 1
    return found
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’opérateur \(in\) pour les listes ?

# default_start
def myIn(items, item):
    found = False                       # 1 affectation
    i = 0                               # 1 affectation
    # len(items) itérations dans le pire cas
    while not found and i < len(items): # 1 negation + 1 comparaison + 1 longueur
        if items[i] == item:            # 1 accès + 1 comparaison
            found = True                # 1 affectation
        i = i + 1                       # 1 affectation + 1 addition
    return found                        # 1 retour
# n = len(items)
# T(n) = 2 + n * (3 + 2 + 2) + 1
#      = 7n + 3
#      = O(n)
# default_end

5 Étendre une liste avec les éléments d’une autre liste (+ operator)

Python permet d’étendre une liste avec les éléments d’une autre liste à l’aide de l’opérateur \(+\).

5.1 Syntaxe

# exercice: show
# default_start
# Étendre une liste avec les éléments d'une autre liste
listName1 = listName2 + listName3
# default_end

5.2 Exemple

# exercice: demo
# default_start
items1 = [1, 2, 3]
print("items1:", items1)
items2 = [4, 5]
print("items2:", items2)
items3 = items1 + items2
print("items3:", items3)
items3 = items3 + [6, 7]
print("items3:", items3)
# default_end

5.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(lists):
    result = []
    for lst in lists:
        result = result + lst
    return result
# default_end
# test_start
print(mystere([[1, 2], [3, 4], [5]]))
print("C683AKRMaR")
print(mystere([["a", "b"], ["c"], ["d", "e"]]))
print("C683AKRMaR")
print(mystere([[], [1, 2], []]))
# test_end
# default_start
def mystere(lists):             # lists = [[1, 2], [3, 4], [5]]
    result = []                 # result = []
    for lst in lists:           # lst = [1, 2]                      lst = [3, 4]                                lst = [5]
        result = result + lst   # result = [] + [1, 2] -> [1, 2]    result = [1, 2] + [3, 4] -> [1, 2, 3, 4]    result = [1, 2, 3, 4] + [5] -> [1, 2, 3, 4, 5]
    return result               # return [1, 2, 3, 4, 5]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’opérateur de listes \(+\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myExtend(list1, list2)\) qui prend en entrée deux listes \(list1\) et \(list2\), et qui retourne une nouvelle liste contenant les éléments de \(list1\) suivis des éléments de \(list2\).

# exercice: design 
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myExtend(list1, list2):
    return None
# default_end
# test_start
print(myExtend([1, 2, 3], [4, 5]))
print("C683AKRMaR")
print(myExtend(["a", "b"], ["c", "d"]))
print("C683AKRMaR")
print(myExtend([1, "a", 2], ["b", 3, "c"]))
print("C683AKRMaR")
print(myExtend([], [1, 2, 3]))
print("C683AKRMaR")
print(myExtend([1, 2, 3], []))
# test_end
# solution_start
def myExtend(list1, list2):
    newList = [0] * (len(list1) + len(list2))
    i = 0
    while i < len(list1):
        newList[i] = list1[i]
        i = i + 1
    j = 0
    while j < len(list2):
        newList[i + j] = list2[j]
        j = j + 1
    return newList
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’opérateur de listes \(+\) ?

# default_start
def myExtend(list1, list2):
    newList = [0] * (len(list1) + len(list2)) # 1 affectation + 1 multiplication + 1 addition
    i = 0                                     # 1 affectation
    # len(list1) itérations
    while i < len(list1):                     # 1 comparaison + 1 longueur
        newList[i] = list1[i]                 # 1 affectation + 1 accès
        i = i + 1                             # 1 affectation + 1 addition
    j = 0                                     # 1 affectation
    # len(list2) itérations
    while j < len(list2):                     # 1 comparaison + 1 longueur
        newList[i + j] = list2[j]             # 1 affectation + 1 accès + 1 addition
        j = j + 1                             # 1 affectation + 1 addition
    return newList                            # 1 retour
# n = len(list1)
# m = len(list2)
# T(n) = 3 + 1 + n * (2 + 2 + 2) + 1 + m * (2 + 2 + 2) + 1
#      = 3n + 3m + 5
#      = O(n + m)
# default_end

6 Trancher une liste avec une plage d’index ([::] operator)

Python permet de trancher une liste avec une plage d’index en utilisant l’opérateur \([::]\) pour créer une sous-liste à partir d’une liste existante ou pour modifier une partie d’une liste.

6.1 Syntaxe

# exercice: show
# default_start
# Accéder à une sous-liste à partir d'un index de départ (défaut 0), un index de fin (défaut len(listName)) et un pas (défaut 1)
sublist = listName[start:end:step] # O(k) où k est la taille de la sous-liste

# Modifier une sous-liste à partir d'un index de départ (défaut 0), un index de fin (défaut len(listName)) et un pas (défaut 1)
listName[start:end:step] = otherListName # O(k) où k est la taille de la sous-liste
# default_end

6.2 Exemple

# exercice: demo
# default_start
list1 = [1, 2, 3, 4, 5, 6]
print("list1:", list1)
list2 = list1[::]
print("list2:", list2)
list3 = list1[1::]
print("list3:", list3)
list3 = list1[::len(list1)-1]
print("list3:", list3)
list4 = list1[0:len(list1):2]
print("list4:", list4)
list1[1:5:2] = ["Hello", "World"]
print("list1:", list1)
# default_end

6.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(items1, items2, start, end, step):
    slice1 = items1[start:end:step]
    slice2 = items2[start:end:step]
    result = slice1 + slice2
    return result
# default_end
# test_start
print(mystere([1, 2, 3, 4, 5], [6, 7, 8, 9, 10], 1, 5, 2))
print("C683AKRMaR")
print(mystere(["a", "b", "c", "d"], ["e", "f", "g", "h"], 0, 4, 2))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4, 5, 6], -1, -4, -1))
# test_end
# default_start
def mystere(items1, items2, start, end, step):     # items1 = [1, 2, 3, 4, 5], items2 = [6, 7, 8, 9, 10], start = 1, end = 5, step = 2
    slice1 = items1[start:end:step]                # slice1 = [2, 4]
    slice2 = items2[start:end:step]                # slice2 = [7, 9]
    result = slice1 + slice2                       # result = [2, 4] + [7, 9] -> [2, 4, 7, 9]
    return result                                  # return [2, 4, 7, 9]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière l’opérateur de listes \([::]\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(mySlicing(list1, start, end, step)\) qui prend en entrée une liste \(items\) et trois entiers \(start\), \(end\) et \(step\), et qui retourne une nouvelle liste contenant les éléments de \(list1\) allant de l’index \(start\) (inclus) à l’index \(end\) (exclus) en prenant un élément tous les \(step\) éléments.

Conseil: réutilisez la fonction \(myRange\) que vous avez écrite précédemment pour générer la liste des index à trancher, puis utilisez ces index pour créer la sous-liste.

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def mySlicing(items, start, end, step):
    return None
# default_end
# test_start
print(mySlicing([1, 2, 3, 4, 5], 0, 3, 1))
print("C683AKRMaR")
print(mySlicing([1, 2, 3, 4, 5], 1, 5, 2))
print("C683AKRMaR")
print(mySlicing([1, 2, 3, 4, 5], -1, -4, -1))
# test_end
# solution_start
def myRange(start, end, step):
    result = None
    if step != 0:
        if start < end and step > 0:
            size = (end - start) // step
            result = [0] * size
            i = 0
            while i < size:
                result[i] = start + i * step
                i = i + 1
        if start > end and step < 0:
            size = (start - end) // (-step)
            result = [0] * size
            i = 0
            while i < size:
                result[i] = start + i * step
                i = i + 1
    return result

def mySlicing(items, start, end, step):
    indexes = myRange(start, end, step)
    i = 0
    result = [0] * len(indexes)
    while i < len(indexes):
        index = indexes[i]
        if index < 0:
            index = len(items) + index
        result[i] = items[index]
        i = i + 1
    return result
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de l’opérateur de listes \([::]\) ?

# default_start
def mySlicing(items, start, end, step):
    indexes = myRange(start, end, step) # O((end - start) / step) 
    i = 0                               # 1 affectation
    result = [0] * len(indexes)         # 1 affectation + 1 multiplication
    # len(indexes) itérations, dans le pire cas len(items) itérations
    while i < len(indexes):             # 1 comparaison + 1 longueur      
        index = indexes[i]              # 1 affectation + 1 accès
        if index < 0:                   # 1 comparaison
            index = len(items) + index  # 1 affectation + 1 longueur + 1 addition
        result[i] = items[index]        # 1 affectation + 1 accès
        i = i + 1                       # 1 affectation + 1 addition
    return result                       # 1 retour
# n = (end - start) / step
# T(n) = O(n) + 1 + 2 + n * (2 + 2 + 1 + 3 + 2 + 2) + 1
#      = O(n) + 1 + 2 + 10n + 1
#      = O(n)
# default_end

7 Ajouter un élément à la fin de la liste (append() method)

Python permet d’ajouter un élément à la fin d’une liste à l’aide de la méthode \(append()\). La méthode \(append()\) modifie la liste en place.

7.1 Syntaxe

# exercice: show
# default_start
# Ajouter un élément à la fin de la liste
listName.append(item) 
# default_end

7.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
items.append(4)
print("items:", items)
# default_end

7.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(items1, items2):
    result = []
    for item in items1:
        result.append(item)
    for item in items2:
        result.append(item)
    return result
# default_end
# test_start
print(mystere([1, 2, 3], [4, 5, 6]))
print("C683AKRMaR")
print(mystere(["a", "b"], ["c", "d"]))
print("C683AKRMaR")
print(mystere([1, "a"], [2, "b"]))
# test_end
# default_start
def mystere(items1, items2):   # items1 = [1, 2, 3], items2 = [4, 5, 6]
    result = []                # result = []
    for item in items1:        # item = 1                   item = 2                    item = 3
        result.append(item)    # result = [1]               result = [1, 2]             result = [1, 2, 3]
    for item in items2:        # item = 4                   item = 5                    item = 6
        result.append(item)    # result = [1, 2, 3, 4]      result = [1, 2, 3, 4, 5]    result = [1, 2, 3, 4, 5, 6]
    return result              # return [1, 2, 3, 4, 5, 6]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de listes \(append()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myAppend(items, item)\) qui prend en entrée une liste \(items\) et un élément \(item\), et qui ajoute l’élément à la fin de la liste. La fonction doit retourner la liste modifiée.

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myAppend(items, item):
    return None
# default_end
# test_start
print(myAppend([1, 2, 3], 4))
print("C683AKRMaR")
print(myAppend(["a", "b"], "c"))
print("C683AKRMaR")
print(myAppend([], 1))
# test_end
# solution_start
def myAppend(items, item):
    newList = [0] * (len(items) + 1)
    i = 0
    while i < len(items):
        newList[i] = items[i]
        i = i + 1
    newList[len(items)] = item
    return newList
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de listes \(append()\) ?

# default_start
def myAppend(items, item):
    newList = [0] * (len(items) + 1)  # 1 affectation + 1 multiplication + 1 addition
    i = 0                             # 1 affectation
    # len(items) itérations
    while i < len(items):             # 1 comparaison + 1 longueur
        newList[i] = items[i]         # 1 affectation + 1 accès
        i = i + 1                     # 1 affectation + 1 addition
    newList[len(items)] = item        # 1 affectation + 1 accès
    return newList                    # 1 retour
# n = len(items)
# T(n) = 3 + n * (2 + 2) + 1
#      = 4n + 4
#      = O(n)
# default_end

8 Trouver l’index d’un élément dans une liste (index() method)

Python permet de trouver l’index de la première occurrence d’un élément dans une liste à l’aide de la méthode \(index()\).

8.1 Syntaxe

# exercice: show
# default_start
# Trouver l'index d'un élément dans une liste
index = listName.index(item)
# default_end

8.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
index = items.index(2)
print("index:", index)
# default_end

8.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(list1, list2):
    results = []
    for item in list2:
        if item in list1:
            results.append(list1.index(item))
    return results
# default_end
# test_start
print(mystere([1, 2, 3], [2, 3]))
print("C683AKRMaR")
print(mystere(["a", "b", "c"], ["b", "c"]))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4]))
# test_end
# default_start
def mystere(list1, list2):                      # list1 = [1, 2, 3], list2 = [2, 3]
    results = []                                # results = []
    for item in list2:                          # item = 2                   item = 3
        if item in list1:                       # 2 in [1, 2, 3] -> True     3 in [1, 2, 3] -> True
            results.append(list1.index(item))   # results = [1]               results = [1, 2]
    return results                              # return [1, 2]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de listes \(index()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myIndex(items, item)\) qui prend en entrée une liste \(items\) et un élément \(item\), et qui retourne l’index de la première occurrence de l’élément dans la liste. Si l’élément n’est pas présent dans la liste, la fonction doit retourner \(None\).

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myIndex(items, item):
    return None
# default_end
# test_start
print(myIndex([1, 2, 3], 2))
print("C683AKRMaR")
print(myIndex(["a", "b", "c"], "b"))
print("C683AKRMaR")
print(myIndex([1, 2, 3], 4))
# test_end
# solution_start
def myIndex(items, item):
    i = 0
    index = None
    while index == None and i < len(items):
        if items[i] == item:
            index = i
        i = i + 1
    return index
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de listes \(index()\) ?

# default_start
def myIndex(items, item):
    i = 0                                   # 1 affectation
    index = None                            # 1 affectation
    # len(items) itérations dans le pire cas
    while index == None and i < len(items): # 1 comparaison + 1 comparaison + 1 longueur
        if items[i] == item:                # 1 accès + 1 comparaison
            index = i                       # 1 affectation
        i = i + 1                           # 1 affectation + 1 addition
    return index                            # 1 retour
# n = len(items)
# T(n) =  1 + 1 + n * (3 + 2 + 2) + 1
#      = 8n + 3
#      = O(n)
# default_end

9 Supprimer la première occurrence d’un élément dans une liste (remove() method)

Python permet de supprimer la première occurrence d’un élément dans une liste à l’aide de la méthode \(remove()\). La méthode \(remove()\) modifie la liste en place.

9.1 Syntaxe

# exercice: show
# default_start
# Supprimer la première occurrence d'un élément dans une liste
listName.remove(item) # O(n)
# default_end

9.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3, 2]
print("items:", items)
items.remove(2)
print("items:", items)
# default_end

9.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(list1, list2):
    for item in list2:
        if item in list1:
            list1.remove(item)
    return list1
# default_end
# test_start
print(mystere([1, 2, 3, 2], [2, 3]))
print("C683AKRMaR")
print(mystere(["a", "b", "c"], ["b", "c"]))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4]))
# test_end
# default_start
def mystere(list1, list2):                  # list1 = [1, 2, 3, 2], list2 = [2, 3]
    for item in list2:                      # item = 2                      item = 3
        if item in list1:                   # 2 in [1, 2, 3, 2] -> True     3 in [1, 3, 2] -> True
            list1.remove(item)              # list1 = [1, 3, 2]             list1 = [1, 2]
    return list1                            # return [1, 2]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de listes \(remove()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myRemove(items, item)\) qui prend en entrée une liste \(items\) et un élément \(item\), et qui retourne une nouvelle liste contenant les éléments de \(items\) sauf la première occurrence de l’élément donné. Si l’élément n’est pas présent dans la liste, la fonction doit retourner la liste inchangée.

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myRemove(items, item):
    return None
# default_end
# test_start
print(myRemove([1, 2, 3, 2], 2))
print("C683AKRMaR")
print(myRemove([1, 2, 3], 4))
print("C683AKRMaR")
print(myRemove([], 1))
# test_end
# solution_start
def myRemove(items, item):
    result = []
    # rechercher l'index de la première occurrence de item dans items
    index = None 
    i = 0
    while index == None and i < len(items):
        if items[i] == item:
            index = i
        i = i + 1
    # si item n'est pas présent dans items, copier items dans result
    if index == None:
        result = [0] * len(items)
        i = 0
        while i < len(items):
            result[i] = items[i]
            i = i + 1
    # si item est présent dans items, alors cela revient à faire un pop() à l'index trouvé
    else:
        result = [0] * (len(items) - 1)
        i = 0
        while i < index:
            result[i] = items[i]
            i = i + 1
        i = index + 1
        while i < len(items):
            result[i - 1] = items[i]
            i = i + 1
    return result
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de listes \(remove()\) ?

# default_start
def myRemove(items, item):
    result = []                            # 1 affectation
    index = None                           # 1 affectation
    i = 0                                  # 1 affectation
    # len(items) itérations dans le pire cas
    while index == None and i < len(items):# 1 comparaison + 1 comparaison + 1 longueur
        if items[i] == item:               # 1 accès + 1 comparaison
            index = i                      # 1 affectation
        i = i + 1                          # 1 affectation + 1 addition
    if index == None:                     # 1 comparaison
        i = 0                              # 1 affectation
        while i < len(items):              # len(items) itérations -> 1 comparaison + 1 longueur
            result[i] = items[i]           # 1 affectation + 1 accès
            i = i + 1                      # 1 affectation + 1 addition
    else:
        i = 0                              # 1 affectation
        while i < index:                  # index itérations -> 1 comparaison
            result[i] = items[i]           # 1 affectation + 1 accès
            i = i + 1                      # 1 affectation + 1 addition
        i = index + 1                     # 1 affectation + 1 addition
        while i < len(items):              # (len(items) - index - 1) itérations -> 1 comparaison + 1 longueur
            result[i - 1] = items[i]       # 1 affectation + 1 accès + 1 addition
            i = i + 1                      # 1 affectation + 1 addition
    return result                        # 1 retour
# n = len(items)
# T(n) = 3 + n * (1 + 1 + 1) + 1 + 1 + 1) + 1 + n * (1 + 1) + 1 + index * (1 + 1) + 1 + (n - index - 1) * (1 + 1 + 1) + 1
#      = 3 + 3n + 3 + 1 + 2n + 1 + 2 * index + 1 + 3 * (n - index - 1) + 1
#      = 8n - index + 10
#      = O(n)
# default_end

10 Compter le nombre d’occurrences d’un élément dans une liste (count() method)

Python permet de compter le nombre d’occurrences d’un élément dans une liste à l’aide de la méthode \(count()\).

10.1 Syntaxe

# exercice: show
# default_start
# Compter le nombre d'occurrences d'un élément dans une liste
count = listName.count(item) # O(n)
# default_end

10.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3, 2]
print("items:", items)
count = items.count(2)
print("count:", count)
# default_end

Exercice

10.2.1 Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(list1, list2):
    results = []
    for item in list2:
        results = results + [list1.count(item)]
    return results
# default_end
# test_start
print(mystere([1, 2, 3, 2], [2, 3]))
print("C683AKRMaR")
print(mystere(["a", "b", "c"], ["b", "c"]))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4]))
# test_end
# default_start
def mystere(list1, list2):                      # list1 = [1, 2, 3, 2], list2 = [2, 3]
    results = []                                # results = []
    for item in list2:                          # item = 2                  item = 3
        results = results + [list1.count(item)] # results = [2]             results = [2, 1]
    return results                              # return [2, 1]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de listes \(count()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myCount(items, item)\) qui prend en entrée une liste \(items\) et un élément \(item\), et qui retourne le nombre d’occurrences de l’élément dans la liste.

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myCount(items, item):
    return None
# default_end
# test_start
print(myCount([1, 2, 3, 2], 2))
print("C683AKRMaR")
print(myCount([1, 2, 3], 4))
print("C683AKRMaR")
print(myCount([], 1))
# test_end
# solution_start
def myCount(items, item):
    count = 0
    i = 0
    while i < len(items):
        if items[i] == item:
            count = count + 1
        i = i + 1
    return count
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de listes \(count()\) ?

# default_start
def myCount(items, item):
    count = 0                       # 1 affectation
    i = 0                           # 1 affectation
    # len(items) itérations
    while i < len(items):           # 1 comparaison + 1 longueur
        if items[i] == item:        # 1 accès + 1 comparaison
            count = count + 1       # 1 affectation + 1 addition
        i = i + 1                   # 1 affectation + 1 addition
    return count                    # 1 retour
# n = len(items)
# T(n) = 2 + n * (2 + 2) + 1
#      = 6n + 3
#      = O(n)
# default_end

11 Inverser une liste (reverse() method)

Python permet d’inverser une liste à l’aide de la méthode \(reverse()\). La méthode \(reverse()\) modifie la liste en place.

11.1 Syntaxe

# exercice: show
# default_start
# Inverser une liste
listName.reverse() # O(n)
# default_end

11.2 Exemple

# exercice: demo
# default_start
items = [1, 2, 3]
print("items:", items)
items.reverse()
print("items:", items)
# default_end

11.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(list1, list2, mode):
    firsts = []
    for item in list1:
        firsts.append(item)

    seconds = []
    for item in list2:
        seconds.append(item)

    if mode == "first":
        firsts.reverse()

    if mode == "second":
        seconds.reverse()

    if mode == "both":
        firsts.reverse()
        seconds.reverse()

    results = firsts + seconds

    return results
# default_end
# test_start
print(mystere([1, 2, 3], [4, 5], "first"))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4, 5], "second"))
print("C683AKRMaR")
print(mystere([1, 2, 3], [4, 5], "both"))
# test_end
# default_start
def mystere(list1, list2, mode):    # list1 = [1, 2, 3], list2 = [4, 5], mode = "first"
    firsts = []                     # firsts = []
    for item in list1:              # item = 1                  item = 2                  item = 3
        firsts.append(item)         # firsts = [1]               firsts = [1, 2]             firsts = [1, 2, 3]

    seconds = []                    # seconds = []
    for item in list2:              # item = 4                  item = 5
        seconds.append(item)        # seconds = [4]              seconds = [4, 5]

    if mode == "first":             # "first" == "first" -> True
        firsts.reverse()            # firsts = [3, 2, 1]

    if mode == "second":            # "first" == "second" -> False

    if mode == "both":              # (non exécuté)

    results = firsts + seconds      # results = [3, 2, 1] + [4, 5] -> results = [3, 2, 1, 4, 5]

    return results                  # return [3, 2, 1, 4, 5]
# default_end

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de listes \(reverse()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(myReverse(list1)\) qui prend en entrée une liste \(list1\) et qui retourne une nouvelle liste contenant les éléments de \(list1\) dans l’ordre inverse.

# exercice: design 
# forbidden_keywords:
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def myReverse(list1):
    return None
# default_end
# test_start
print(myReverse(["a", "b", "c"]))
print("C683AKRMaR")
print(myReverse([1, 2, 3, 4]))
print("C683AKRMaR")
print(myReverse([1]))
print("C683AKRMaR")
print(myReverse([]))
# test_end
# solution_start
# OPTION 1
def myReverse(list1):
    reversedList = [0] * len(list1)
    i = 0
    while i < len(list1):
        reversedList[i] = list1[len(list1) - 1 - i]
        i = i + 1
    return reversedList

# OPTION 2
def myReverse(list1):
    reversedList = []
    i = 0
    while i < len(list1):
        reversedList.insert(0, list1[i])
        i = i + 1
    return reversedList
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de liste \(reverse()\) ?

# default_start
def myReverse(list1):
    reversedList = [0] * len(list1)                     # 1 création de la liste + 1 longueur
    i = 0                                               # 1 affectation
    while i < len(list1):                               # len(list1) itérations -> 1 comparaison + 1 longueur
        reversedList[i] = list1[len(list1) - 1 - i]     # 1 affectation + 1 longueur + 1 soustraction + 1 accès + 1 affectation
        i = i + 1                                       # 1 addition + 1 affectation
    return reversedList                                 # 1 retour
# default_end

12 Trier une liste (sort() method)

Python permet de trier une liste par ordre croissant à l’aide de la méthode \(sort()\). La méthode \(sort()\) modifie la liste en place.

12.1 Syntaxe

# exercice: show
# default_start
# Trier une liste
listName.sort()
# default_end

12.2 Exemple

# exercice: demo
# default_start
items = [3, 1, 2, 5, 4]
print("items:", items)
items.sort()
print("items:", items)
# default_end

12.3 Exercice

Comprendre

Quelle est la sortie de ce programme ?

# default_start
def mystere(list1, mode):
    results = None
    if mode in ["0", "1", "2"]:
        results = []
        for item in list1:
            results.append(item)
        if mode == "1":
            results.sort()
        if mode == "2":
            results.sort()
            results.reverse()
    return results
# default_end
# test_start
print(mystere([1, 4, 3, 2], "0"))
print("C683AKRMaR")
print(mystere([1, 4, 3, 2], "1"))
print("C683AKRMaR")
print(mystere([1, 4, 3, 2], "2"))

# test_end
# default_start
def mystere(list1, mode):           # list1 = [1, 4, 3, 2], mode = "2"
    results = None
    if mode in ["0", "1", "2"]:     # "2" in ["0", "1", "2"] -> True
        results = []                # results = []
        for item in list1:          # item = 1                  item = 4                  item = 3                  item = 2
            results.append(item)    # results = [1]             results = [1, 4]          results = [1, 4, 3]       results = [1, 4, 3, 2]
        if mode == "1":             # "2" == "1" -> False
            results.sort()          # (non exécuté)
        if mode == "2":             # "2" == "2" -> True
            results.sort()          # results.sort() -> results = [1, 2, 3, 4]
            results.reverse()       # results.reverse() -> results = [4, 3, 2, 1]
    return result                   # return [4, 3, 2, 1]

Concevoir

Découvrez l’algorithme qui se cache derrière la méthode de liste \(sort()\) en utilisant uniquement les fondamentaux et les fonctionnalités de base des listes que nous avons vus jusqu’à présent.

Écrire une fonction \(mySort(list1)\) qui prend en entrée une liste \(list1\) et qui retourne une nouvelle liste contenant les éléments de \(list1\) triés par ordre croissant.

# exercice: design
# forbidden_keywords: for, in
# forbidden_functions: input, sum, max, min, sorted, range, enumerate, zip, abs, all, any, dir, eval, reversed, map, filter
# forbidden_structures: set, tuple, frozenset, bytearray, bytes
# forbidden_list_methods: negative_indexing, slicing, append, extend, index, count, remove, sort, add, contains, reversed, gt, ge, lt, le, eq
# forbidden_dict_methods: reversed, or, ior, ror, contains
# default_start
def mySort(list1):
    return None
# default_end
# test_start
print(mySort([4, 2, 3, 1]))
print("C683AKRMaR")
print(mySort([5, 4, 3, 2, 1]))
print("C683AKRMaR")
print(mySort([1, 2, 3]))
# test_end
# solution_start
def mySort(list1):
    sortedList = [0] * len(list1)
    # copy list1 to sortedList
    i = 0
    while i < len(list1):
        sortedList[i] = list1[i]
        i = i + 1
    # bubble sort algorithm
    i = 0
    while i < len(sortedList):
        j = 0
        while j < len(sortedList) - 1 - i:
            if sortedList[j] > sortedList[j + 1]:
                temp = sortedList[j]
                sortedList[j] = sortedList[j + 1]
                sortedList[j + 1] = temp
            j = j + 1
        i = i + 1
    return sortedList
# solution_end

Analyser

D’après votre implémentation, quelle est la complexité en temps de la méthode de liste \(sort()\) ?

# default_start
def mySort(list1):
    sortedList = [0] * len(list1)                       # 1 création de la liste + 1 longueur
    i = 0                                               # 1 affectation
    while i < len(list1):                               # len(list1) itérations -> 1 comparaison + 1 longueur
        sortedList[i] = list1[i]                        # 1 affectation + 1 accès
        i = i + 1                                       # 1 addition + 1 affectation
    i = 0                                               # 1 affectation
    while i < len(sortedList):                          # len(sortedList) itérations -> 1 comparaison + 1 longueur
        j = 0                                           # 1 affectation
        while j < len(sortedList) - 1 - i:              # (len(sortedList) - 1 - i) itérations -> 1 comparaison + 1 longueur
            if sortedList[j] > sortedList[j + 1]:       # 1 accès + 1 comparaison + 1 accès + 1 comparaison
                temp = sortedList[j]                    # 1 affectation + 1 accès
                sortedList[j] = sortedList[j + 1]       # 1 affectation + 1 accès
                sortedList[j + 1] = temp                # 1 affectation
            j = j + 1                                   # 1 addition + 1 affectation
        i = i + 1                                       # 1 addition + 1 affectation
    return sortedList                                   # 1 retour
# n = len(list1)
# T(n) = 1 + 1 + n * (1 + 1) + 1 + n * (1 + 1) + 1 + n * (n - 1 - i) * (1 + 1 + 1 + 1) + 1
#      = 2 + 2n + 1 + 2n + 1 + 4n * (n - 1 - i) + 1
#      = 4n^2 - 4n * i + 6n + 5
#      = O(n^2)
# default_end