IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Recherche élément médian dans tableau non trié


Sujet :

Algorithmes et structures de données

  1. #1
    Membre régulier
    Inscrit en
    Décembre 2003
    Messages
    99
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 99
    Points : 82
    Points
    82
    Par défaut Recherche élément médian dans tableau non trié
    Bonjour,

    J'ai un tableau d'entiers non trié, j'aimerais savoir quel est la meilleure méthode pour retrouver l'element qui a la valeur mediane.

    La méthode que j'utilise pour le moment c'est un trie du tableau. Puis ensuite je recupere l'élément à l'indice (Taille du tableau/2).

    J'aimerais savoir si il est possible de faire la meme chose sans trier tout le tableau ? Voir sans le trier ?

    Merci.
    "Il n'existe que deux choses infinies, l'univers et la bêtise humaine... mais pour l'univers, je n'ai pas de certitude absolue." A. Einstein

  2. #2
    Membre éclairé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Points : 763
    Points
    763
    Par défaut
    Je ne vois pas bien l'intérêt de ton algorithme en fait ??
    Tu veux récupérer quelle valeur ?
    Celle qui serait au milieu du tableau une fois celui-ci trié sans le trier
    Ou tu veux récupérer la valeur moyenne (ce qui n'aurait alors rien à voir !)...
    Aucune réponse à une question technique par MP.
    Ce qui vous pose problème peut poser problème à un(e) autre

    http://thebrutace.labrute.fr

  3. #3
    Membre régulier
    Inscrit en
    Décembre 2003
    Messages
    99
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 99
    Points : 82
    Points
    82
    Par défaut
    Salut,

    Oui effectivement c'est pas tres clair ; en fait voila mon probleme :

    J'ai un tableau du style :

    [12,1,15,89,100,123,456,23,5555,987]

    J'aimerai recuperer l'element du milieu (une fois le tableau trie).

    C'est à dire 23.

    Pour le moment la seule méthode que je voit c'est de trier le tableau puis de prendre l'element du milieu. (C'est long) car je repete cette operation N*M fois !

    Donc j'aimerais savoir si il est possible de recuperer 23 plus rapidement. Peut etre en ne triant pas totalement le tableau, en adaptant un algorithme de trie specifique à mon probleme ?
    "Il n'existe que deux choses infinies, l'univers et la bêtise humaine... mais pour l'univers, je n'ai pas de certitude absolue." A. Einstein

  4. #4
    Modérateur
    Avatar de ggnore
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    2 472
    Détails du profil
    Informations personnelles :
    Âge : 45
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 2 472
    Points : 4 029
    Points
    4 029
    Par défaut
    Il y a différentes méthodes de tri de tableau.

    As tu essayé Quicksort ?
    Toutes les vertus des hommes se perdent dans l’intérêt comme les fleuves se perdent dans la mer.
    N'oubliez pas de consulter les FAQ Linux et les cours et tutoriels Linux

  5. #5
    Membre régulier
    Inscrit en
    Décembre 2003
    Messages
    99
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 99
    Points : 82
    Points
    82
    Par défaut
    Oui effectivement j'utilise le QuickSort. Il est rapide c'est vrai O(nlogn).

    Je me pose juste la question : "Est-ce possible de créer son propre algo pour récupérer l'élément du milieu plus rapidement qu'en O(nlogn) ?".

    Je sais qu'il est prouvé qu'on ne peut pas trier un tableau plus rapidement que le quickSort.(Sauf dans des cas très specifiques).

    En fait, dois-je forcement trier tout le tableau ou alors en triant que des parties specifiques du tableau je peux atteindre mon but ( Variante du trie insertion/dichotomique, ou du tri SHELL ).

    Pour finir, dans le cas d'un QuickSort, les perfomances sont dépandes du choix de l'element pivot, qui varie au cours de l'algo. Quel serait le choix à faire pour cet élément dans mon cas ?
    "Il n'existe que deux choses infinies, l'univers et la bêtise humaine... mais pour l'univers, je n'ai pas de certitude absolue." A. Einstein

  6. #6
    Membre régulier Avatar de kaisse
    Profil pro
    Inscrit en
    Novembre 2003
    Messages
    100
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2003
    Messages : 100
    Points : 117
    Points
    117
    Par défaut
    Il est possible d'avoir l'élément médian en temps linéaire: c'est d'ailleurs ce qui permet (de manière théorique) de faire baisser la complexité du quick sort en pire des cas en 0(nlogn). Seulement l'algo est un peu embetant à expliquer. Cherche "médiane en temps linéaire" sur Google, ou emprunte un Cormen si tu es à la fac/dans une école.

    En gros, ca consiste à considérer des paquets de 5 éléments de ton tableau, à trouver la médiane pour chaque (temps constant, car de taille constante (5)), à prendre la médiane des médianes (appel récursif) puis à partitionner ton tableau autour de cette médiane. Si elle a bien la place d'une médiane: c'est cool, sinon, il te faut réiterer soit à droite soit à gauche de ta médiane. Sachant que cette fois tu ne veux plus la place du milieu, mais celle qui te sépare du milieu: i.e. si tu avais 10 éléments, qu'après avoir appliqué l'algo, tu te retrouves en place 3, tu appelles l'algo sur les 7 éléments restant, mais tu ne veux pas la médiane de ces 7 éléments restant (qui serait l'élément numéro 7), tu veux le 2ème élément (3 + 2 =5)

    Bon, je sais, c'est pas clair du tout, mais j'ai pas beaucoup de temps là, et il faut en prendre pour expliquer clairement cet algorithme.

  7. #7
    Membre régulier
    Inscrit en
    Décembre 2003
    Messages
    99
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 99
    Points : 82
    Points
    82
    Par défaut
    Salut, merci pour cette piste.

    J'ai fait effectivement un petit tour sur google et j'ai trouvé mon bonheur dans cette presentation powerPoint pour ceux que ca interesse, je met le lien (Ya plein d'algo sur les tris, le quick select...).

    http://faculty.concordia.edu/jeff_sl...%20lecture.ppt

    La conclusion est que l'on peut effectivement trouvé le kième element d'un tableau non trié en temps linéaire ! C'est effectivement ce qui permet de garantir que le quickSort est toujours en O(nlogn).

    Merci Kaisse .
    "Il n'existe que deux choses infinies, l'univers et la bêtise humaine... mais pour l'univers, je n'ai pas de certitude absolue." A. Einstein

  8. #8
    Membre du Club
    Profil pro
    Inscrit en
    Février 2007
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2007
    Messages : 134
    Points : 57
    Points
    57
    Par défaut
    Bonjour,

    Je relance ce (très) vieux topic pour une petite question. J'ai mis en place l'algorithme expliqué et je souhaiterais connaitre la complexite de cet algorithme dans le pire des cas en fonction du nombre de comparaisons d'éléments du tableau et la complexité moyenne toujours en fonction du nombre de comparaisons.

    Merci par avance pour votre aide !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 6
    Dernier message: 11/05/2014, 11h29
  2. Recherche élément commun dans deux tables
    Par marime dans le forum Langage SQL
    Réponses: 4
    Dernier message: 24/05/2011, 17h27
  3. [XL-2007] Copie, recherche, insertion, données dans tableau
    Par stephst84 dans le forum Macros et VBA Excel
    Réponses: 11
    Dernier message: 21/05/2010, 17h52
  4. Recherche de doublons dans tableau
    Par mavean dans le forum Excel
    Réponses: 4
    Dernier message: 04/08/2008, 00h42
  5. Réponses: 3
    Dernier message: 16/12/2002, 17h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo