Aller au contenu

Chap. 10. Algorithmes de recherche et de tri

Algorithmes de recherche

Algorithmes de tri

Tri par sélection

Implémentation en Python

Fonctions auxiliaires

Permutation

La fonction permuter prend en paramètre un tableau tab et deux entiers i1 et i2 correspondant à des indices valides de tab. Cette fonction ne renvoie rien mais modifie tab en échangeant les éléments aux indices i1 et i2.

Exemple : 

>>> tab1 = [10, 11, 12, 13, 14]
>>> permuter(tab1, 2, 4)
>>> tab1
[10, 11, 14, 13, 12]

Codes à trous 
1
2
3
4
def permuter(tab, i1, i2):
    tmp = ...
    tab[i2] = ...
    tab[...] = ...

1
2
3
4
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[...]
    tab[i1] = ...

1
2
3
4
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[...]
    tab[i1] = tmp
Correction 
1
2
3
4
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[i1]
    tab[i1] = tmp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def permuter(tab, i1, i2):
    # On mémorise dans une variable temporaire l'élément
    # situé à la position i2.
    tmp = tab[i2]
    # On copie l'élément situé en position i1 à la position i2.
    # Résultat : cet élément est présent deux fois dans le
    # tableau.
    tab[i2] = tab[i1]
    # On place dans la case d'indice i1 la valeur de tmp qui
    # contient l'élément initialement placé en i2.
    tab[i1] = tmp
Minimum à partir d’un rang i

La fonction minimum prend en paramètre un tableau tab et un rang valide i. Cette fonction renvoie la position j_min de la valeur minimum du tableau à partr du rang i. Autrement dit, la recherche du minimum se limite à la partie du tableau allant du rang i à la fin du tableau.

Exemple :

>>> #        0   1   2   3   4   5   6   7
>>> tab1 = [32, 13, 17, 10, 45, 15, 12, 21]
>>> minimum(tab1, 0)
3 # le minimum est 10 situé à la position 3
>>> minimum(tab1, 4)
6 # le minimum est 12 situé à la position 6
Codes à trous 
1
2
3
4
5
6
def minimum(tab, i):
    j_min = ...
    for j in ...:
        if ...:
            j_min = ...
    return ...

1
2
3
4
5
6
def minimum(tab, i):
    j_min = ...
    for j in range(..., len(tab)):
        if tab[j] < ...:
            j_min = ...
    return j_min

1
2
3
4
5
6
def minimum(tab, i):
    j_min = ...
    for j in range(i, len(tab)):
        if tab[j] < tab[...]:
            j_min = ...
    return j_min
Correction 
1
2
3
4
5
6
def minimum(tab, i):
    j_min = i
    for j in range(i, len(tab)):
        if tab[j] < tab[j_min]:
            j_min = j
    return j_min

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def minimum(tab, i):
    # Au départ, le premier élément de la zone de recherche est choisie
    # comme minimum provisoire. Le rang du minimum provisoire j_min
    # est donc initialisé à i (le premier rang de la zone de
    # recherche).
    j_min = i
    # On parcourt le tableau à partir du rang i.
    for j in range(i, len(tab)):
        # Si l'élément courant est plus petit que le minimum
        # provisoire,
        if tab[j] < tab[j_min]:
            # le minimum provisoire devient l'élément courant. Cela
            # prend effet en mettant à jour le rang du minimum qui
            # prend la valeur du rang courant.
            j_min = j
    # En fin de parcours, j_min correspond au rang du minimum de la
    # zone de recherche.
    return j_min

Fonction principale

Tri par sélection

La fonction tri_selection prend en paramètre un tableau tab. Cette fonction ne renvoie rien mais modifie tab en triant ses éléments dans l’ordre croissant.

Exemple : 

>>> tab1 = [45, 3, 24, 8, 6, 90]
>>> tri_selection(tab1)
>>> tab1
[3, 6, 8, 24, 45, 90]

Codes à trous 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[i1]
    tab[i1] = tmp

def minimum(tab, i):
    j_min = i
    for j in range(i, len(tab)):
        if tab[j] < tab[j_min]:
            j_min = j
    return j_min

def tri_selection(tab)
    for i in range(len(tab)):
        i_min = ...
        ...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    def permuter(tab, i1, i2):
        tmp = tab[i2]
        tab[i2] = tab[i1]
        tab[i1] = tmp

    def minimum(tab, i):
        j_min = i
        for j in range(i, len(tab)):
            if tab[j] < tab[j_min]:
                j_min = j
        return j_min

    def tri_selection(tab)
        for i in range(len(tab)):
            i_min = ...
            permuter(tab, ..., ...)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[i1]
    tab[i1] = tmp

def minimum(tab, i):
    j_min = i
    for j in range(i, len(tab)):
        if tab[j] < tab[j_min]:
            j_min = j
    return j_min

def tri_selection(tab)
    for i in range(len(tab)):
        i_min = minimum(tab, ...)
        permuter(tab, i, ...)
Correction 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[i1]
    tab[i1] = tmp

def minimum(tab, i):
    j_min = i
    for j in range(i, len(tab)):
        if tab[j] < tab[j_min]:
            j_min = j
    return j_min

def tri_selection(tab)
    for i in range(len(tab)):
        i_min = minimum(tab, i)
        permuter(tab, i, i_min)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def permuter(tab, i1, i2):
    tmp = tab[i2]
    tab[i2] = tab[i1]
    tab[i1] = tmp

def minimum(tab, i):
    j_min = i
    for j in range(i, len(tab)):
        if tab[j] < tab[j_min]:
            j_min = j
    return j_min

def tri_selection(tab)
    # On parcourt le tableau
    for i in range(len(tab)):
        # Étape 1. On identifie le minimum de la zone restant à trier.
        i_min = minimum(tab, i)
        # Étpae 2. On permute le minimum avec l'élément en début de 
        # la zone restant à trier.
        permuter(tab, i, i_min)

Tri par insertion

Implémentation en Python

La fonction tri_insertion prend en paramètre un tableau tab. Cette fonction ne renvoie rien mais modifie tab en triant ses éléments dans l’ordre croissant.

Exemple : 

>>> tab1 = [45, 3, 24, 8, 6, 90]
>>> tri_insertion(tab1)
>>> tab1
[3, 6, 8, 24, 45, 90]

Codes à trous 
1
2
3
4
5
6
7
8
def tri_insertion(tab):
    for i in ...:
        cle = ...
        j = ...
        while j >= ... and ...:
            tab[j + 1] = ...
            ...
        ... = cle

1
2
3
4
5
6
7
8
def tri_insertion(tab):
    for i in range(len(tab)):
        cle = tab[...]
        j = ...
        while j >= ... and tab[j] > ...:
            tab[j + 1] = tab[...]
            ...
        tab[...] = cle

1
2
3
4
5
6
7
8
def tri_insertion(tab):
    for i in range(len(tab)):
        cle = tab[...]
        j = i - 1
        while j >= ... and tab[j] > ...:
            tab[j + 1] = tab[...]
            j -= 1 # j = j - 1
        tab[j + 1] = cle
Correction 
1
2
3
4
5
6
7
8
def tri_insertion(tab):
    for i in range(len(tab)):
        cle = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1 # j = j - 1
        tab[j + 1] = cle

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def tri_insertion(tab):
    # On parcourt le tableau
    for i in range(len(tab)):
        # 1. On mémorise la clé.
        cle = tab[i]
        # 2. On fait les décallages.
        j = i - 1
        while j >= 0 and tab[j] > cle:
            tab[j + 1] = tab[j]
            j -= 1 # j = j - 1
        # 3. On replace la clé au bon endroit.
        tab[j + 1] = cle