Aller au contenu

Sélection☘

Dans cette page, on va mettre en oeuvre le principe de tri par sélection (présenté dans la page index). La liste triée sera ici une nouvelle liste (dans la page suivante, la liste triée sera la liste de départ elle-même).

Exercice☘

Écrire un code pour le corps de la fonction suivante:

def rechercheMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'élément de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 2, 8, 3])
    8
    """
Un code possible
def rechercheMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'élément de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 2, 8, 3])
    8
    """
    assert tab != [], "Attention, la liste doit être non vide."
    m = tab[0] #contiendra le max
    for element in tab:
        if element > m: m = element
    return m


# TESTS
from random import randint
L = [randint(-10,10) for _ in range(randint(5,9))]
# on teste notre fonction en utilisant la fonction python prédéfinie:
print(rechercheMax(L) == max(L))
Complément: en JS

La fonction pourrait être codée ainsi en javascript:

function rechercheMax(tab){
    /* 
    tab -- tableau (type array) d'entiers non vide 

    renvoie l'élément de valeur maximale parmi les éléments de tab.
    */
    console.assert(tab.length != 0, "Attention, le tableau doit être non vide");
    let m = tab[0];
    for(let element of tab){
        if(element > m){ m = element;}
    }
    return m;   
}

Ce fichier html reprend ce code et montre un exemple d'utilisation (rappelons que vous pouvez voir le code de la page html à l'aide d'un clic droit en sélectionnant "code source de la page".)

Exercice☘

Pour traduire le principe exposé en page d'entrée, Cassien propose le code suivant:

def rechercheMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'élément de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 2, 8, 3])
    8
    """
    m = tab[0] #contiendra le max
    for element in tab:
        if element > m: m = element
    return m



def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        m = rechercheMax(resteATrier)
        listeTriee = [m] + listeTriee
        resteATrier = [x for x in resteATrier if x != m]

    return listeTriee


# TESTS

A = [2, 9, 1, 3, -5, -7, 23, 42, -666]
B = triSelection(A)
print(B)
Complément: en JS

Le code de Cassien en javascript.

Donner un exemple de liste montrant que la fonction triSelection ainsi définie n'est pas correcte.

Une liste non triée par triSelection

Il suffit de prendre une liste où certaines valeurs sont plusieurs fois présentes. En effet, dans le code 

[x for x in resteATrier if x != m]
on supprime toutes les valeurs égales à m, au lieu de n'en supprimer qu'une.

Exercice☘

On veut corriger le problème du code proposé par Cassien.

Une première stratégie.☘

Une première stratégie consiste à avoir une fonction qui renvoie l'indice du maximum plutôt que la valeur du maximum. On peut ainsi remplacer le code [x for x in resteATrier if x != m] par un code qui éliminera l'unique valeur ayant l'indice du maximum, les autres valeurs égales à ce maximum sont ainsi préservées et seront ajoutées à la variable listeTriee aux tours de boucle suivant.

Codez cette stratégie.

Solution
def rechercheIndiceMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'indice d'un élément 
    de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 4, 8, 3])
    2
    """
    m = tab[0] # sera le max
    indice = 0 # sera l'indice du max
    for i, element in enumerate(tab):
        if element > m: 
            m = element
            indice = i
    return indice

def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        indice_m = rechercheIndiceMax(resteATrier)
        maximum = resteATrier[indice_m]
        listeTriee = [maximum] + listeTriee
        resteATrier = [x for i, x in enumerate(resteATrier) if i != indice_m]

    return listeTriee


# TESTS
A = [3, 2, 9, 1, 3, -5, -7, 23, 42, -666, 9, 3]
B = triSelection(A)
print(B)
# test avec fonction python prédéfinie:
A.sort()
print(A==B)

Une seconde stratégie.☘

Une seconde stratégie consiste à ne pas ajouter une seule valeur à la fois à la variable listeTriee: on peut choisir d'ajouter à listeTriee la valeur m autant de fois qu'elle est présente dans la variable resteATrier.

Codez cette stratégie.

Solution
def rechercheMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'élément de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 2, 8, 3])
    8
    """
    m = tab[0] #contiendra le max
    for element in tab:
        if element > m: m = element
    return m



def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        m = rechercheMax(resteATrier)
        listeTriee = [x for x in tab if x==m] + listeTriee
        resteATrier = [x for x in resteATrier if x != m]

    return listeTriee

Exercice☘

Python propose une méthode pop sur les listes. 

>>> a = [666, 42, 1789, 1515]
>>> b = a.pop(1)
>>> b
42
>>> a
[666, 1789, 1515]

a désignant une liste python et i un indice de cette liste, après l'instruction b = a.pop(i), b a pour valeur a[i] et la liste a a perdu cet élément.

En d'autres termes, l'intruction b = a.pop(i) a un effet similaire à la succession d'instructions:

b = a[i]
a = [ a[j] for j in range(len(a)) if j != i]

Illustration en reprenant l'exemple ci-dessus:

>>> a = [666, 42, 1789, 1515]
>>> b = a[1]
>>> b
42
>>> a = [ a[j] for j in range(len(a)) if j != 1]
>>> a
[666, 1789, 1515]
Important

Les codes:

b = a.pop(i)

et 

b = a[i]
a = [ a[j] for j in range(len(a)) if j != i]

ne sont pas équivalents, car le premier agit en place sur la liste a (c'est à l'objet liste initial que l'on enlève un élément) tandis que le second crée une nouvelle liste a.

Réécrivez la fonction de tri par sélection de l'exercice précédent (version stratégie 1) en utilisant pop.

Un code possible

On a simplement raccourci un peu l'expression de la boucle dans triSelection:

def rechercheIndiceMax(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'indice d'un élément 
    de valeur maximale parmi les éléments de tab.
    >>> rechercheMax([7, 4, 8, 3])
    2
    """
    m = tab[0] # sera le max
    indice = 0 # sera l'indice du max
    for i, element in enumerate(tab):
        if element > m: 
            m = element
            indice = i
    return indice

def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        indice_m = rechercheIndiceMax(resteATrier)
        listeTriee = [resteATrier.pop(indice_m)] + listeTriee


    return listeTriee


# TESTS
from random import randint
A = [randint(-10, 10) for _ in range(0, randint(5,15))]
B = triSelection(A)
print(B)
# test avec fonction python prédéfinie:
A.sort()
print(A == B)

Exercice☘

Réécrire les deux versions du tri insertion proposées ci-dessus
mais avec une sélection du minimum à la place d'une sélection du maximum.

Stratégie indice du minimum
def rechercheIndiceMin(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie l'indice d'un élément de valeur minimale  
    parmi les éléments de tab.
    >>> rechercheMin([7, 4, 8, 1, 9, 1])
    3
    """
    m = tab[0] # sera le min
    indice = 0 # sera l'indice du min
    for i, element in enumerate(tab):
        if element < m: 
            m = element
            indice = i
    return indice

def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        indice_m = rechercheIndiceMin(resteATrier)
        minimum = resteATrier[indice_m]
        listeTriee = listeTriee + [minimum]
        resteATrier = [x for i, x in enumerate(resteATrier) if i != indice_m]

    return listeTriee


# TESTS
A = [3, 2, 9, 1, 3, -5, -7, 23, 42, -666, 9, 3]
B = triSelection(A)
print(B)
# test avec fonction built-in
A.sort()
print(A==B)
Stratégie multicopie du min
def rechercheMin(tab):
    """
    tab -- liste d'entiers non vide 

    renvoie un élément de valeur minimale 
    parmi les éléments de tab.
    >>> rechercheMin([7, 2, 8, 3])
    2
    """
    m = tab[0] #contiendra le min
    for element in tab:
        if element < m: m = element
    return m




def triSelection(tab):
    """
    tab -- liste d'entiers

    renvoie une liste contenant les mêmes éléments 
    que tab mais triée en ordre croissant.
    """
    listeTriee = []
    resteATrier = [x for x in tab]

    while resteATrier != []:
        minimum = rechercheMin(resteATrier)
        listeTriee = listeTriee + [x for x in resteATrier if x == minimum]
        resteATrier = [x for x in resteATrier if x != minimum]

    return listeTriee


# TESTS
A = [3, 2, 9, 1, 3, -5, -7, 23, 42, -666, 9, 3]
B = triSelection(A)
print(B)
# test avec fonction built-in
A.sort()
print(A==B)