Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 20/03/2024 14:00:00
Submission limit No limitation

Sign in

Sign in

[TP.05] Tri stable

Le problème du tri, comme la plupart des problèmes, peut être appréhendé selon différentes perspectives. Une approche classique consiste à utiliser les opérateurs de comparaison tels que < ou >= définissant un ordre naturel sur les éléments à trier.

Une alternative équivalente consiste à associer à chaque objet un nombre réel, appelé clé, et l’ordre d’un ensemble d’objets correspond à l’ordre ascendant naturel défini sur leurs clés. Autrement dit, un nombre réel est attribué a chaque objet et les objets sont triés par ordre croissant de clé.

Il peut arriver que plusieurs objets soient associés à la même clé. Il s’agit d’un exemple de ce que l’on appelle un ordre partiel. En d’autres mots, il existe des paires d’éléments différents tel qu’aucun des deux éléments ne précède l’autre. Cette situation introduit une incertitude, ou en tout cas une ambiguïté, sur le résultat d’un tri si l’on ne définit pas de contrainte supplémentaire. La question est donc de savoir comment ordonner des objets de clés identiques. Ce problème est le plus souvent résolu en imposant la propriété de stabilité. Un algorithme de tri est dit stable s’il conserve l’ordre relatif original des éléments qui possèdent la même clé.

Par exemple :

S05_1_4_stable_search/stable_sort.png

Dans l’exemple précédent, la clé associée à chaque oeuvre d’H. P. Lovecraft correspond à son année d’édition. Plusieurs objets possèdent la même clé :

  • 1927 The Dream Quest of Unknow Kadath et The Colour out of Space ;
  • 1932 The Shadow over Innsmouth et The Dreams in the Witch-House.

The Dream Quest of Unknow Kadath doit apparaître avant The Colour out of Space dans la séquence triée afin de respecter le même ordre que la séquence initiale. De la même manière, The Shadow over Innsmouth doit être placé avant The Dreams in the Witch-House.

Tri par sélection stable

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier searcher.py qui contient la signature de la fonction et quelques exemples de tests.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

Attention : Le tri est croissant.

class book():
    '''
    Classe représentant un livre, correspondant à une paire nom-année d'édition
    '''
    #...some code

def selection_sort_stable(books):
    """
    pre: `books` est un tableau (list) de `book`
    post: tri par sélection STABLE du tableau passé en paramètre.
        Les éléments sont triés en place
    """