🚀 go-pugleaf

"Pierre" <curl_TRACE@netcourrier.com> writes:

> Bonjour,
> Ma question ne porte pas sp�cifiquement sur le C, mais plutot sur
> l'algorithmie. (D�sol� pour ce l�ger HS)
> 
> Voila,
> je cherche � trouver les n premiers maxima dans un tableau de N �lements.
> Je me creuse la t�te pour trouver un algorithme simple, et rapide (..DSP..),
> mais je n'ai manifestement pas trouv� la m�thode qui me convienne.
> (je r�alise n passes pour trouver � chaque fois le maximum) ..
> 
> Quelqu'un a une suggestion , un lien, une id�e ??

De memoire:

* Tu conserves un tableau trie de n elements et tu inseres dedans a
  chaque fois si c'est necessaire.  n N au pire mais en moyenne ca
  doit etre meilleur.

* Heapsort en limitant le nombre de recherche a n (l'initialisation du
  tas est en N, l'extraction en log N, donc on est en N + n log N)

* quicksort en sautant les recursions dans la zone qui n'interesse
  pas.  A nouveau au pire nN mais en moyenne mieux.

Le probleme est traite dans Knuth.

XPost&FU2: fr.comp.developpement, le groupe approprie sous fr.*
(Note: j'avais marque le XPost mais oublie de le faire dans une
premiere version).

-- 
Jean-Marc
FAQ de fclc:       http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org