Discussion :

[prgasp77]

Bonjour,
le calcul de la médiane, si je ne suis pas devenu fou, se fait simplement en modifiant un quicksort (qui complet est en n.log(n)) en ne triant que la moitié contenant le milieu du tableau :

Ci-après,
() : nombre pivot
|| : milieu du tableau d'origine (il faudra garder une trace de la position du sous tableau traitée dans le tableau d'origine pour déterminer la position médiane)

[5 9 4 3 8 |4| 5 4 7 1 2]
[(5) 9 4 3 8 |4| 5 4 7 1 2]
[4 3 4 5 4 |1| 2 (5) 9 8 7]
[4 3 4 5 4 |1| 2 5]
[(4) 3 4 5 4 |1| 2 5]
[3 4 4 1 2 |(4)| 5 5]

Médiane -> 4.

Cdlt,

[prgasp77]

Ou en log(n)

[souviron34]

Bonjour,
le calcul de la médiane, si je ne suis pas devenu fou, se fait simplement en modifiant un quicksort (qui complet est en n.log(n)) en ne triant que la moitié contenant le milieu du tableau :

Le PO n'a pas droit au tri

Et c'était un exercice.. Merci de ne pas donner l'ensemble des solutions toutes faites

[prgasp77]

Le PO n'a pas droit au tri

Si je lis bien entre les lignes de la réponse de son professeur, il n'a pas le droit de « trier puis trouver la médiane » ; en revanche il semble pouvoir modifier judicieusement l'ordre des éléments de son tableau (tri partiel) pour pouvoir trouver le saint graal la médiane.

Et c'était un exercice.. Merci de ne pas donner l'ensemble des solutions toutes faites

Si le PO cherchais une solution toute faite, il aurait sûrement déjà trouvé cette publication*. Non, la démarche de ce dernier me semble indiquer qu'il cherche à comprendre et apprendre, peut êter même au delà de son exercice. Et apprendre à implémenter / adapter un algo décrit (et non donné) dans un article fait aussi parti de l'apprentissage non ?

(*) second résultat chez moi de google « median finding ».

[souviron34]

Si je lis bien entre les lignes de la réponse de son professeur, il n'a pas le droit de « trier puis trouver la médiane » ; en revanche il semble pouvoir modifier judicieusement l'ordre des éléments de son tableau (tri partiel) pour pouvoir trouver le saint graal la médiane.

Sans doute...

Mais ma solution marche aussi vite (en termes de complexité seulement) et sans invoquer de tri (donc de mémoire supplémentaire si on veut garder le tableau intact)

Si le PO cherchais une solution toute faite, il aurait sûrement déjà trouvé cette publication*. Non, la démarche de ce dernier me semble indiquer qu'il cherche à comprendre et apprendre, peut êter même au delà de son exercice. Et apprendre à implémenter / adapter un algo décrit (et non donné) dans un article fait aussi parti de l'apprentissage non ?

(*) second résultat chez moi de google « median finding ».

Ok, j'ai peut-être été un peu vite

[prgasp77]

Sans doute...

Mais ma solution marche aussi vite (en termes de complexité seulement) et sans invoquer de tri (donc de mémoire supplémentaire si on veut garder le tableau intact)

Dans ce cas effectivement elle est meilleure. Mais la mienne s'explique en une phrase

En réalité, je suis incapable de calculer la complexité de mon quicksort modifié. Comment procéder ?

[souviron34]

En réalité, je suis incapable de calculer la complexité de mon quicksort modifié. Comment procéder ?

puisque c'est la même base que le quicksort ou la dichotomie, ce devrait être aussi en log(N).


PS: en plus, ma solution ne dépendant pas d'un tri, le pire cas est le cas moyen . O on fait entre 1 fois et log(N) fois l'itération

log N
2

[Celelibi]

[*]Calcul de la médiane

Code :

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
27
 
milieu = N/2
Diff = milieu
Ref = moy
 
Faire jusqu'à ce que Diff <= 1
 
   m = 0
   pour i = 1 jusqu'à N
       si val(i) <= Ref
           m = m + 1
       fin si
   fin pour
 
   si m < milieu
      Diff = milieu - m
      Delta = (max - Ref)/2
      min = Ref
      Ref = Ref + Delta
   sinon
      Diff = m - milieu
      Delta = (Ref-min)/2
      max = Ref
      Ref = Ref - Delta
   fin si
 
fin faire

[/LIST]

C'est bien INDEPENDANT des valeurs, et c'est bien en O(N) (moyenne) et log(N)*N (médiane).

FAUX !
Ta condition a beau être sur le nombre de valeur du tableau, tu n'as aucune garantie que ta valeur Diff diminue à chaque itération. La valeur de Diff dépend (linéairement) de m qui elle-même dépend de la valeur de Ref. Ref qui évolue dans l'espace des valeurs du tableau.

Mais bon, je vais arrêter là tellement tu es têtu.
Cela dit, si un jour te prend l'envie de tester ton propre algo, essaye-le sur les listes suivantes :
[0, 1, 2, 3, 34]
-> Ton algo donne 1 (résultat faux) en 3 itérations

[0, 1, 2, 3, 4]
-> Résultat 1 en 1 itération

[0, 1, 3, 4]
-> Résultat 1 en 1 itération

[0, 1, 2, 3]
-> Résultat 2 en 1 itération

[0, 1, 2, 3, 2^4000]
-> Résultat 1 en 3998 itérations

[0, 0, 0, 1]
-> Ne termine pas

[Celelibi]

En réalité, je suis incapable de calculer la complexité de mon quicksort modifié. Comment procéder ?

C'est du O(N).
À la première itération tu examines N valeurs, puis à la seconde itération, tu examines en moyenne N/2 valeurs. Puis N/4, puis N/8.

N + N/2 + N/4 + ... + N/N = N* ( 1 + 1/2 + 1/4 + ... + 1/N)
Or 1/2 + 1/4 + ... = 1.
Donc N < N*(1 + 1/2 + 1/4 + ... + 1/N) < N*2.

C'est donc du O(N) en moyenne. Cela dit, dans le pire des cas, il est en O(N²).
Cet algo s'appelle quickselect.

[prgasp77]

C'est du O(N).
À la première itération tu examines N valeurs, puis à la seconde itération, tu examines en moyenne N/2 valeurs. Puis N/4, puis N/8.

Ha… oui, tout simplement.

Cet algo s'appelle quickselect.

Merci beaucoup.

[mat1554]

Bon, vu que le prof disait que le défi et sans trier, mais possibilité de faire sans tous trier. J'essais encore de le faire sans trie Orgueilleux que je suis ^^

Code :

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
27
28
29
30
31
32
33
Indice = 0                                 
Ecart = NbrElement/2                                   
total = tab[Indice]                                
Pointeur = Indice+1                                
 
Si NbrElement%2 == 0                                   
    Qte = 2                            
 
Pour Indice < NbrElement                                
    Pivot = tab[Indice]                            
    total += tab[Indice]                               
 
    Pour Pointeur < NbrElement                              
        Si (Pointeur <> Indice) && (Ecart >= 0)    // Ne pas comparer 1 nombre a lui-même.    
            Si tab[Pointeur] < Pivot                    
                Ecart--                
        Pointeur++                         
 
        Si (Ecart == 0) && (NbrElement%2 != 0)  // Impair 1 seul réponse       
            Med = Pivot                    
        sinon si (Ecart == 0) && (NbrElement%2 == 0) && (Qte==2)    // 1ère valeur pair
            Tempo = Pivot                      
            Qte--                      
            Ecart = NbrElement/2                       
            Indice++                       
            Pointeur = 0                       
        sinon si (Ecart == 0) && (NbrElement%2 == 0) && (Qte==1)    // Seconde valeur pair
            Med = (Tempo+Pivot)/2                      
        sinon                          
            Ecart = NbrElement/2                       
            Indice++                       
            Pointeur = 0                       
    Indice++

Cependant, si j'ai un tableau avec un NbrElement pairs, ça ne fonctionne pas, car lors de mon passage dans Ecart pour l’élément que j'ai besoin il a comme valeur (1) au lieu de 0.

P.S : Je n'ai cependant pas encore transformer mon algo en C# pour tester. J'ai juste fais une exécution manuelle. Donc il est possible que mon exécution ne soit pas parfaite ^^

Donc, je crois a testé quand je vais avoir 5 min, que dans le cas d'un tableau pair, il me faudrait 2 écart : N/2 & N/2+1.

Je vais voir... Mais si vous avez idée plus simple.

[souviron34]

Cela dit, si un jour te prend l'envie de tester ton propre algo, essaye-le sur les listes suivantes :
[0, 1, 2, 3, 34]
-> Ton algo donne 1 (résultat faux) en 3 itérations

[0, 1, 2, 3, 4]
-> Résultat 1 en 1 itération

[0, 1, 3, 4]
-> Résultat 1 en 1 itération

[0, 1, 2, 3]
-> Résultat 2 en 1 itération

[0, 1, 2, 3, 2^4000]
-> Résultat 1 en 3998 itérations

[0, 0, 0, 1]
-> Ne termine pas

Et qu'aurais-tu , toi, comme médiane, pour chacun de ces tableaux ??

[Celelibi]

Et qu'aurais-tu , toi, comme médiane, pour chacun de ces tableaux ??

Bien... Par définition de la médiane :
[0, 1, 2, 3, 34]
-> 2

[0, 1, 2, 3, 4]
-> 2

[0, 1, 3, 4]
-> 2

[0, 1, 2, 3]
-> 1.5 (n'importe quoi entre 1 et 2 ferait l'affaire)

[0, 1, 2, 3, 2^4000]
-> 2

[0, 0, 0, 1]
-> 0

[souviron34]

Je pige pas la dernière :

[0, 0, 0, 1]
-> 0

ça ne partage pas en 2 parties égales...

nb valeurs <= : 3
n valeurs > : 1

Mais bon....


Sinon effectivement l'algo que j'vais indiqué était bien en O(N log M).. désolé de m'être fourvoyé... (et il marche) .. Mais j'ai une autre idée..

[mat1554]

Je pige pas la dernière :



ça ne partage pas en 2 parties égales...

nb valeurs <= : 3
n valeurs > : 1

Mais bon....


Sinon effectivement l'algo que j'vais indiqué était bien en O(N log M).. désolé de m'être fourvoyé... (et il marche) .. Mais j'ai une autre idée..

Enfaite, la médiane de 0,0,0,1 c'est bien 0. C'est la donnée central du tableau, peu importe le nombre de fois qu'elle se répète. Dans le cas d'un tableau pair.

N/2 & (N/2)+1. Donc = 4/2 & 4/2+1 = 2 et 3. Donc 0+0=0/2 = 0

[prgasp77]

Je pige pas la dernière :



ça ne partage pas en 2 parties égales...

nb valeurs <= : 3
n valeurs > : 1

Mais bon....


Sinon effectivement l'algo que j'vais indiqué était bien en O(N log M).. désolé de m'être fourvoyé... (et il marche) .. Mais j'ai une autre idée..

En fait, dans les cas tordus comme ça, la définition de la médiane ne différencie pas > et ≥. Ainsi, il y a deux valeurs inférieures (0 et 0) et deux supérieures (0 et 1).
C'est la perversité des maths : les cas dégénérés.

[pseudocode]

Algo bête et méchant:

Code :

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

1
2
3
4
5
6
7
TantQue size(Liste)>2
  Retirer la valeur la plus grande
  Retirer la valeur la plus petite
Fin TantQue
 
Si size(Liste)=2, Afficher (Liste[0]+Liste[1])/2
Si size(Liste)=1, Afficher Liste[0]

Garanti sans aucun tri, et en O(N²).

[Celelibi]

ça ne partage pas en 2 parties égales...

nb valeurs <= : 3
n valeurs > : 1

La page wikipedia de la médiane donne des exemples de cas où les nombres sont répétés et pour tous les autres cas de figure.

Mais c'est vrai qu'en donner une définition mathématique rigoureuse et propre n'est pas trivial.

[mat1554]

Algo bête et méchant:

Code :

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

1
2
3
4
5
6
7
TantQue size(Liste)>2
  Retirer la valeur la plus grande
  Retirer la valeur la plus petite
Fin TantQue
 
Si size(Liste)=2, Afficher (Liste[0]+Liste[1])/2
Si size(Liste)=1, Afficher Liste[0]

Garanti sans aucun tri, et en O(N²).

Ouep, mais bon en gros le prof disait de pas toucher au valeur, en parlant de tri. Mais je crois que retirer reviens a touché au valeur aussi ^^.

Mais j'avoue que c'est une version bien bête ça ^^

[prgasp77]

Ouep, mais bon en gros le prof disait de pas toucher au valeur, en parlant de tri. Mais je crois que retirer reviens a touché au valeur aussi ^^.

Retirer la valeur du tableau et se souvenir de ne plus tenir compte de cette valeur dans le tableau, ça revient au même .