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