Discussion :

[contremaitre]

Comme j'ai eu un peu de mal à trouver des informations sur la recherche rapide de médiane, je récapitule ici ce que j'ai trouvé.

Soit n valeurs
Soit Tab le tableau contenant ces valeurs.


Trivial :
Trier les valeurs et prendre la valeur du milieu

Plus efficace :
Sélectionner la n/2 ieme valeur la plus petite grace à un quickselect

Sur un faible nombre de valeurs (et c'est le cas qui m'interesse ici, notamment en traitement d'image) la solution la plus rapide :
Soit la fonction trier :
Si on peut modifier les valeurs d'entrées :
Trier(a,b) inverse a et b si a > b
Si on ne peut pas modifier les valeurs d'entrées :
Il faudra soit tout copier dans un tableau temporaire pour travailler dessus, soit pour gagner un peu de temps, copier tout en triant selon l'étape dans laquelle on est.

Exemple pour 3 valeurs :

Code :

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

1
2
3
 
trier(Tab[0],Tab[1]); trier(Tab[1],Tab[2]); trier(Tab[0],Tab[1]); 
retourner Tab[1];

Pour 5 valeurs

Code :

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

1
2
3
4
 
trier(Tab[0],Tab[1]); trier(Tab[3],Tab[4]); trier(Tab[0],Tab[3]); 
trier(Tab[1],Tab[4]); trier(Tab[1],Tab[2]); trier(Tab[2],Tab[3]); 
trier(Tab[1],Tab[2]); retourner Tab[2];

Pour 9 valeurs

Code :

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

1
2
3
4
5
6
7
8
9
 
trier(Tab[1],Tab[2]); trier(Tab[4],Tab[5]); trier(Tab[7],Tab[8]); 
trier(Tab[0],Tab[1]); trier(Tab[3],Tab[4]); trier(Tab[6],Tab[7]); 
trier(Tab[1],Tab[2]); trier(Tab[4],Tab[5]); trier(Tab[7],Tab[8]); 
trier(Tab[0],Tab[3]); trier(Tab[5],Tab[8]); trier(Tab[4],Tab[7]); 
trier(Tab[3],Tab[6]); trier(Tab[1],Tab[4]); trier(Tab[2],Tab[5]); 
trier(Tab[4],Tab[7]); trier(Tab[4],Tab[2]); trier(Tab[6],Tab[4]); 
trier(Tab[4],Tab[2]); 
retourner Tab[4];

[PRomu@ld]

Plus efficace :
Sélectionner la n/2 ieme valeur la plus petite grace à un quickselect

Pas forcément, dans le pire des cas, tu peux être en O(n^2). Dans ce cas un tri puis la sélection donnera un meilleur résultat. De plus, avec une application en traitement d'image, tu peux très bien faire une modification du tri postal pour avoir en O(n) la médiane.

[PRomu@ld]

Au passage, la selection peut se faire en O(n) même dans le cas défavorable.

Si tu as la possibilité de te procurer le bouquin "Introduction à l'algorithmique" (Cormen, Rivest, Stein, Leiserson), ça fait l'objet d'une partie (9.3 pour la seconde édition)

[contremaitre]

Pas forcément, dans le pire des cas, tu peux être en O(n^2).

Oui le pire des cas est en n^2, mais en O(n) avec une forte probabilité si le pivot est choisi au hazard.

Dans tous les cas on ne peut pas faire plus vite que la dernière méthode, pour un faible nombre de pixels.

Attention : à la fin, ni la liste, ni le début de la liste ne sont triés.


Est ce que tu connais le nom de l'algo en temps linéaire.
J'y suis surement tombé dessus, mais les inconvénients sont soit une grosse consommation de mémoire, soit un algo bien plus compliqué pour un gain nul par rapport au quickselect en pratique

[millie]

Est ce que tu connais le nom de l'algo en temps linéaire.
J'y suis surement tombé dessus, mais les inconvénients sont soit une grosse consommation de mémoire, soit un algo bien plus compliqué pour un gain nul par rapport au quickselect en pratique

Il y a effectivement un algorithme probabiliste en temps linéaire assez simple et un algorithme déterministe en temps linéaire qui est plus compliqué.

Il est souvent appelé : The Linear-Time Finding Median Algorithm

Une implémentation Java que j'ai pu trouver dans ImageJ est la suivante :

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 public static double findNthLowestNumber(double[] buf, int bufLength, int n) {
		// Modified algorithm according to http://www.geocities.com/zabrodskyvlada/3alg.html
		// Contributed by Heinz Klar
        int i,j;
        int l=0;
        int m=bufLength-1;
        double med=buf[n];
        double dum ;
 
        while (l<m) {
            i=l ;
            j=m ;
            do {
                while (buf[i]<med) i++ ;
                while (med<buf[j]) j-- ;
                dum=buf[j];
                buf[j]=buf[i];
                buf[i]=dum;
                i++ ; j-- ;
            } while ((j>=n) && (i<=n)) ;
            if (j<n) l=i ;
            if (n<i) m=j ;
            med=buf[n] ;
        }
    return med ;
    }

A appeler avec :

Code :

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

findNthLowestNumber(buffer, buffer.length, buffer.length/2);

PRomu@ld : sources