Version imprimable
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.
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 8O
Ou tu veux récupérer la valeur moyenne (ce qui n'aurait alors rien à voir !)...
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 y a différentes méthodes de tri de tableau.
As tu essayé Quicksort ?
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 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.
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 :king: .
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 !