Discussion :

[HenryDeNohr]

Bonjour, et bonne année à tous.
Je viens ici car j"'ai un problème avec une annale de concours : Informatique commune 2018, précisément à la 14 qui porte sur un algorithme de tri rapide imposé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def triRapide ( liste ,g , d ) :
    #pivot = # À compléter
    i = g
    j = d
    while True :
        while i <= d and liste [ i ][0] < pivot : i = i +1
        while j >= g and liste [ j ][0] > pivot : j = j -1
        if i > j : break
        if i < j : liste [ i ] , liste [ j ] = liste [ j ] , liste [ i ]
    i = i +1
    j = j -1
    if g < j : triRapide ( liste ,g , j )
    if i < d : triRapide ( liste ,i , d )

les arguments sont une liste à trier et 2 indices.
la liste à trier est une liste L de 2 listes; représentant la hauteur pour la première (liste h) et la période pour la seconde (liste p) de différentes vagues triées dans l'ordre chronologique.
Le but de la question est de compléter la ligne 2 (pivot) et de déterminer la valeur des indices g et d lors du premier appel (fonction récursive) pour trier la liste L selon les valeurs croissantes de la liste h. la liste p doit donc aussi être modifiée pour rester cohérent.

Mon problème, c'est que je comprend pas du tout où veut en venir cette fonction : boucle infinie rompue par un brak, alors que mon prof s'énerve dès qu'on utilise des break, un tri présenté comme "tri rapide" alors qu'il n'a rien à voir avec mon cours, 3 paramètres, et une fonction récursive sans return. C'est courant, les fonctions récursives sans return ? moi c'est la première fois que j'en vois. :/

bref, je coince. vous pouvez m'aider à réponde à cette question s'il vous plaît ?

[wiztricks]

Salut,

et une fonction récursive sans return. C'est courant, les fonctions récursives sans return ? moi c'est la première fois que j'en vois. :/

La "fonction" n'a pas besoin de "return"er quoi que ce soit car elle trie la liste/tableau "in place".
Ce genre d'algo. datant des années 60, il y a plein d'articles sur le sujet qu'un peu de recherche sur Internet vous permettrait de trouver pour avoir explications dans tous les sens et exemples de code.

- W

[tyrtamos]

Bonjour,

Il s'agit bien de l'algorithme de tri rapide "Quicksort" de Tony Hoare publié en 1961 (https://en.wikipedia.org/wiki/Quicksort)

Selon le principe, g et d représente à chaque appel l'indice de début et l'indice de fin de la partie de la liste à trier. Au 1er appel, g et d seront donc le 1er et le dernier indice de la liste.

Quand au pivot, il s'agit couramment de l'élément de la liste situé au milieu de la partie de la liste à trier.

[Pyramidev]

Quand au pivot, il s'agit couramment de l'élément de la liste situé au milieu de la partie de la liste à trier.

Ce n'est pas l'algo recommandé. Robert Sedgewick, qui a fait une thèse sur le tri rapide, conseille de prendre comme pivot le médian parmi le premier élément, celui du milieu et le dernier. Par exemple, pour le tableau [10, 2, 4, 1, 7], on regarde les trois éléments 10, 4 et 7 et on prend le médian de ces trois, c'est-à-dire 7 (car 4 < 7 < 10). Donc, dans mon exemple, on prendrait comme pivot le dernier élément.

[tyrtamos]

Bonjour,

La médiane est effectivement une bonne solution dans le cas général.

En tout cas, le choix du pivot est important, pour éviter une dégradation du temps de traitement en fonction de la présentation des données à trier: aléatoires, déjà partiellement triées (ordre direct ou inverse), etc...

[wiztricks]

La médiane est effectivement une bonne solution dans le cas général.

Paraîtrait que non (selon wikipedia) et la publication en 2009 d'un algo. qui utilise un "dual pivot".


- W

[tyrtamos]

Bonjour wiztricks,

(le lien donné est cassé)

Tout dépend comment on calcule la médiane. Si on veut calculer la "vraie" médiane, cela complexifie le calcul à chaque appel récursif, et ce n'est plus recommandé. Mais une version très simplifiée comme proposé par Pyramidev reste acceptable à mon avis et représente une petite amélioration de la version que j'avais proposée.

Ce tri est très efficace en moyenne, mais pour qu'il le soit dans tous les cas, il y a une foultitude d'améliorations proposées les 50 dernières années. Y compris de changer d'algorithme pour les petites partitions...

[wiztricks]

(le lien donné est cassé)

A priori, c'est réparé.
Sinon il est mentionné dans l'article QuickSort de wikipedia (note 11).

- W