Sélection en place☘

Le tri par sélection écrit en page précédente renvoie une nouvelle liste. On aimerait agir sur la liste initiale, c'est à dire écrire une version du tri par sélection qui ne renvoie rien mais trie la liste initiale.

On s'interdit donc de créer une nouvelle liste, on doit trier en échangeant entre eux des éléments de la liste initiale (mais en respectant l'idée du tri par sélection).

Note

Rappelons ici que trier en place une liste sans création d'une nouvelle liste permet un gain d'utilisation de la mémoire. On travaille avec une seule liste plutôt que deux: avec de grandes listes, le gain peut être important. Un gain en temps est également souvent une conséquence de ce choix du tri en place.

Principe☘

On dispose d'un jeu de cartes et chaque carte est posée dans une "case":

On doit trier le jeu par le principe de sélection du maximum mais on n'a pas le droit de poser les cartes en dehors de la boîte à cases. La seule opération permise est d'échanger deux cartes de place.

Comment pourriez-vous procéder ?

Une réponse

On recherche la plus grande carte et on l'échange avec la carte occupant la dernière case:

On ne touchera plus à la partie à fond jaune.
On recommence: on cherche, dans la partie à fond blanc, la plus grande carte et on l'échange avec la carte occupant la dernière position blanche:

On recommence: on cherche, dans la partie à fond blanc, la plus grande carte et on l'échange avec la carte occupant la dernière position blanche:

On recommence: on cherche, dans la partie à fond blanc, la plus grande carte et on l'échange avec la carte occupant la dernière position blanche:

et ainsi de suite jusqu'à ce que tout le fond soit jaune.

Exercice☘

Écrire une version de la fonction rechercheIndiceMax suivant la spécification suivante:

def rechercheIndiceMax(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur maximale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 1,3)
    3
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 0,3)
    0
    """

Solution

def rechercheIndiceMax(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur maximale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 1,3)
    3
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 0,3)
    0
    """
    m = tab[debut] # sera le max de tab[debut..fin]
    indice = debut # sera l'indice du max de tab[debut..fin]
    for i in range(debut+1, fin+1):
        if tab[i] > m:
            m = tab[i]
            indice = i
    return indice

Exercice☘

Écrire maintenant une version du tri par sélection du maximum qui trie en place la liste passée en argument.

Principe

On note n le nombre d'éléments de la liste tab.
Le principe est le suivant:

rechercher l'indice im du max de tab[0..(n-1)]
échanger les valeurs de tab[im] et de tab[n-1].
rechercher l'indice im du max de tab[0..(n-2)]
échanger les valeurs de tab[im] et de tab[n-2].
rechercher l'indice im du max de tab[0..(n-3)].
échanger les valeurs de tab[im] et de tab[n-3].
etc...

A chaque étape, la queue de liste est triée et contient les valeurs maximales; le début de liste reste à trier.

Solution

Un code possible:

def rechercheIndiceMax(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur maximale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 1,3)
    3
    >>> rechercheIndiceMax([15, 6, 7, 8, 9], 0,3)
    0
    """
    m = tab[debut] # sera le max de tab[debut..fin]
    indice = debut # sera l'indice du max de tab[debut..fin]
    for i in range(debut+1, fin+1):
        if tab[i] > m:
            m = tab[i]
            indice = i
    return indice




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

    Modifie tab en triant ses éléments en ordre croissant.
    """
    for i in range(0, len(tab)-1):
        im = rechercheIndiceMax(tab, 0, len(tab)-1-i)
        tab[len(tab)-1-i], tab[im] = tab[im], tab[len(tab)-1-i]




# TESTS
from random import randint
A = [randint(-10,10) for i in range(randint(1, 10))]
# test de notre tri avec le tri built-in:
B = [x for x in A]
triSelection(A)
B.sort()
print(A == B)

Exercice☘

Réécrire le tri par sélection en place de l'exercice précédent mais par une sélection du minimum.

Adaptation du principe

Dans la version avec max, on plaçait le maximum en fin de liste et on faisait évoluer l'indice marquant la fin de liste restant à trier.

Dans la version avec min, on place les min en début de liste en faisant évoluer l'indice marquant le début de liste restant à trier.

Solution

Un code possible:

def rechercheIndiceMin(tab, debut, fin):
    """
    tab -- liste d'entiers non vide 
    debut -- indice de tab
    fin -- indice de tab

    renvoie l'indice (debut <= indice <= fin) d'un élément 
    de valeur minimale parmi les éléments de tab[debut..fin].
    >>> rechercheIndiceMin([15, 6, 7, 8, 9], 1,3)
    1
    >>> rechercheIndiceMin([15, 6, 7, 8, 9], 0,3)
    1
    """
    m = tab[debut] # sera le min de tab[debut..fin]
    indice = debut # sera l'indice du min de tab[debut..fin]
    for i in range(debut+1, fin+1):
        if tab[i] < m:
            m = tab[i]
            indice = i
    return indice




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

    Modifie tab en triant ses éléments en ordre croissant.
    """
    for i in range(0, len(tab)-1):
        im = rechercheIndiceMin(tab, i, len(tab)-1)
        tab[i], tab[im] = tab[im], tab[i]




# TESTS
from random import randint
A = [randint(-10,10) for i in range(randint(1, 10))]
# test de notre tri avec le tri built-in:
B = [x for x in A]
triSelection(A)
B.sort()
print(A == B)