Reprise du message précédent :

Tu obtiens 2 séquences (u) et (v) disjointes avec p termes d'un côté et q termes de l'autre telles que les ensembles {u} et {v} sont disjoints. Par contre tu ne connais par le cardinal de ces ensembles. Tu sais juste que Card{u}<=p et que Card{v}<=q.
 
Si tu as pris soin de supprimer le pivot en décomptant ses redondances au fur et à mesure (on sait jamais: si c'était lui l'élu), tu peux même te démerder pour que p + q < N ce qui permet de supprimer à coup sûr l'une des deux séquences.
 
Par contre, il suffit qu'on n'ait pas de bol (genre pivot mal choisi dans le tri rapide) pour se retrouver avec (u) riquiqui et tout le problème à nouveau concentré dans (v):
 
(u) = (-1,0) | (v) = (3,5,6,3,6,8,3,3,10,3,3,3)
 
Et même dans le cas excellent où <<l'un des ensembles ne contient qu'une seule valeur>> (càd où une séquence est redondante à 100%), j'aimerais savoir comment on le vérifie sans faire un nouveau parcours?
 
Le O(n) n'est pas encore gagné, là...
Pourtant la philosophie du tri rapide est prometteuse...

Ben le principe c'est une fois séparé en 2 ensembles de te retapper un tri rapide sur le plus gros des 2 ( vu que tu a dors et déjà éliminer la valeur pivot, tu à p+q< N, et si ton pivot était présent plus de n/2 fois, tu l'as remarquer en faisant tes comparaisons ). Si tu n'as qu'une seule valeur dedans, tu le remarquera en faisant tes comparaisons. ( je supose donc qu'à chaque étape du tri rapide, tu compte le nombre de fois ou tu as égalité avec ton pivot et tu supprime ces valeurs pour l'éventuelle étape suivante ).
Il est clair que l'algo est bien plus rapide que le tri rapide, puisqu'à chaque étape :
- tu élimine les valeures redondantes
- tu ne refait l'étape suivante que sur le plus grand des deux ensembles.

 
Tom, on est tout à fait d'accord sur le principe de décompte/suppression du pivot puisque je le suggérais moi-même dans mon intervention (<<Si tu as pris soin de supprimer le pivot en décomptant ses redondances au fur et à mesure (on sait jamais: si c'était lui l'élu>> ), mais ça répond pas à la question posée. On peut se choper régulièrement un pivot merdique non-redondant.
 
NB. - Je précise la question: c'est pas parce que ton pivot est un peu redondant, genre 33% des voix, que c'est lui l'élu (s'il y a un élu). Imagine que tu te retrouves avec (u) riquiqui, 33% dans le pivot (on vire car 33%<50%) et (v) totalement redondant: (v)=(x,x,x,x,...,x)
Comment tu fais pour vérifier que (v) ne contient que des x sans les parcourir. Le tri rapide t'a permis seulement de comparer les termes avec le pivot, pas les termes entre eux.

voui, j'avais bien compris, c'est pour ça que je te redétaillais le bazar : la première passe te permet d'éliminer une partie de tes données, mais il faut continuer tant que tu n'as pas soit trouver un pivot présent plus de n/2 fois, soit que tu n'as plus qu'un paquet de taille inférieur à n/2. ( i.e. si l'élu est dans v, à un moment, il sera pivot, en au plus n/2 étape de tri, et en général en 1 ou 2 étape, puisque statistiquement, tu as plus d'une chance sur 2 de tombé dessus )
donc dans le cas que tu donne, il te faut recommencer une phase de tri rapide avec v, et tu recommencera tant que tes sous-ensembles sont de taille > n/2.  
Mais a priori, tu atteindras très vite ce résultat ( en une ou 2 étapes ), mais dans le pire des cas, il te faudra n/2 étapes de tri pour y arriver, soit une complexité en O(n2) ...  Je suppose donc que ce n'est pas exactement la solution de la prof en question...

je peux t'en faire une de tête ...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
mince elle est O(N)  

Je qui me chiffonne, c'est qu'on n'a pas utilisé intelligemment le fait que si un entier x apparaît au moins n/2 fois dans la séquence, alors il apparaît 1 fois sur 2 en moyenne...
 
Peut-être qu'on pourrait faire un tri rapide avec une autre relation d'ordre ou en moulinant sur les paires au lieu de mouliner sur les unités. (?)

Ben oui, mais en même temps, si un élément apparait N/2 - 1 fois, t'as quasi le même rapport, donc c'est pas suffisant.
Plus j'y pense, et plus je crois qu'il n'y a pas de vraiment meilleure solution que celle proposée avec le tri rapide. Ca m'agace de pas trouver mieux ...

 
Je suis desolé mais si tu applique le tri rapide tel quel (meme si tu ne tri pas le tableau entierement), ton algo reste de complexité idem a celle du tri rapide : O(Nlog(N))    
...que tu divise en 2 ton tableau exactement log(N) fois (dans le cas ou le pivot est tjs bien choisi...et que dans ce cas te mene a un tableau final trié) ou bien que tu le divise en 2 non pas exactement log(N) fois mais (log(N) - X) fois, la complexité reste en O(Nlog(N))  
 
EDIT: pour en complexité O(N), il faut un algo dont on parcourir le tableau (complexité N donc) auquel on AJOUTE une constante !

quelqu'un a une expérience avec gperf ?

 
  gperf : "A perfect hash function generator"    
-> je la connais la fonction de hachage "parfaite" sans collision pour ce probleme : c'est d'utiliser un tri par comptage

 
Pas totalement d'accord. On n'a pas trouvé, ok, mais on a au moins montré que:
- d'une part on économise le pivot et ses redondances à chaque redivision (on s'en débarrasse purement et simplement si son compteur est < n/2 (sinon c'est fini))
- d'autre part on ne triera pas les deux sous-séquences puisqu'une seule nous intéresse à chaque fois (l'autre dégage si sa longueur est < n/2: on s'en fout de la trier)
 
Donc le principe du tri rapide est quand même très nettement amélioré. Maintenant il manque une astuce qui hisse tout ça vers O(N)...

oui mais c'est du o(N) mémoire ...
joue avec gperf si tu veux

justement non, si le pivot est bien choisi à chaque fois, tu fait pas plus de 2 ou 3 itérations ! Si tu suppose que tu divise bie nton tableau en 2 à chaque fois, en 2 itérations, tu as fini -> soit en 3n/2 comparaisons. Faut bien comprendre que dans le cas générale, le nombre de passe sera de l'ordre de 2 ou 3, puisqu'à chaque passe tu divise grosso modo tes possibilités par 2. Dans l'estimation du tri, pour donner O(nlog(n)) on suppose bien que tu sépare en 2 sous ensemble de p et q éléments avec Card(q) ~= n/2, d'où la complexité C(N) = 2C(N/2) -> O(Nlog(n)). Ma méthode donne plutot C(N) = C(N/2) + P(N) où P(N) est une v.a.r dépendante de ton pivot mais qui a une esperance de 2. (m'enfin, c'est heuristique, il faudrait une preuve un plus mathématiques qui repose moins sur des estimation de probabilités )

 
Si tu appliques directement le tri rapide a cet exemple (tu prends par exemple le pivot, la derniere val du tableau) :
 
tableau contient : 1111122222 2222211111
 
tu effectues log(N) divisions ... ce qui reste du Nlog(N) non ?    
d'autre part, comment veux-tu savoir si la valeur du pivot (a chaque recursion) est la meme N/2 fois ? : ici le pivot prendra la val 1, 5 fois, puis la valeur 2, 10fois.
Enfin bref, c un algo largement plus proche du O(Nlog(N)) que du O(N)...suffit d'appliquer sur un tableau de plusieurs millions d'elment et tu verras vers kel tps tu penches le plus (tri rapide ou bien le tri comptage).

Y'a pas à dire, les langages C et dérivés c'est vraiment naze...
 
En ADA, un tableau de -100000000000 à 100000000000 n'occupera en mémoire que les lignes qui y sont remplies, donc au pire des cas, il occupera la même place que le tableau d'origine...
 
Sinon, y'a une solution pour "émuler" le fonctionnement d'ADA... Au lieu d'utiliser un tableau, tu utilises un arbe, ou une liste chaînée (ce qu'ADA fait en interne). Mais là tu fait exploser la complexité de l'algo...

Je répète que l'algo que nous proposons n'est pas strictement le tri rapide. Pour l'échantillon que tu proposes et avec le pivot que tu proposes, il répond OUI en exactement 14 passes (c'est même inférieur à N!) et ne procédera à aucune division. Tu sembles ne pas comprendre les améliorations suggérées plus haut.
 
En fait, la pire configuration pour notre algo est la suivante:
1,2,3,4,5,....,1000,1001,1001,1001,1001,... si on prend le pivot en début de vecteur! Là c'est la cata et on se retrouve dans le contexte de complexité maximale du tri rapide traditionnel.
Dans les cas plus moyens, l'estimation de tomlameche est assez réaliste même si elle demande une confirmation mathématique.
 
Tout ce que je peux concéder, c'est qu'on n'a pas atteint le O(N) garanti. Mais c'est bcp mieux qu'un tri rapide.

Bon, pour arrêter de parler dans le vide, voilà un pseudo-code qui marchouille (avec des variables "gros sabots" pour fixer les idées):
 

Bon de toute façon, le principe est de trouver la médiane, et ensuite de vérifier si cette mediane est présente n/2 fois.
Or, le fait est qu'il existe un algo qui permet d'obtenir la mediane d'un ensemble numérique en un temps linéaire, mais je me rappelle plus exactement comment ça marche    

On m'a présenté un algo très astucieux pour résoudre ce problème :

L'algo est donc bien en O(n).
La démo de cet algo n'est pas évidente, et comme c'est un bon exercice, je vous laisse la chercher    
   
 

Ah, j'adore ce genre d'algo....
Au début c'est   et enfin après reflexion :    
 
Je me demande quand même comment les auteurs peuvent trouver ça !
 
Au fait, qqun aurait un lien sur un bon site d'algortihmique qui proposerait des algos de ce type (les seuls que je trouve sont sur les algo classique : tri, stucture,...)
 

 
ouai ben des algos comme ça en exam, le prof peut se les garder où je pense    
c t un devoir "seulement" de 2h avec
ex1 (7pts)
ex2 (5pts, c t celui la )
ex3 (8pts)
 
Merci a tous qd meme pour la reflexion au sujet  

 
Très bonne idée, ca marche...PRESQUE ! ... donc en fait ca marche pas
C'est très simple, j'ai coder ton algo + le "meme" mais en O(n²) pour la verif; résultat : en generant des valeurs aléatoires entre 0 et 2 dans un tableau de 10 cases, ca marche les 5/6 du tps mais je suis tombé sur une configuration précise pour laquelle ton algo foire (je n'ai pas la configuration sous les yeux, j'éditerai mon message plus tard pour te la montrer).
 
Dommage    
 
PS : tu avais testé avant de poster ?
 
EDIT : ton algo ne marche pas avec ce vecteur : 1101202121

Il y a bien un algo pour trouver en O(n) le kieme élément dans une liste une fois celle-ci triée non ?
 
Il suffit alors de prendre le k=n/3 ieme element et le k=2n/3 ieme. Votre candidat à la place de nombre present n/2 fois au moins est un de ces 2 là.

Il est possible que j'ai mal retranscris l'algo, je l'ai tapé de mémoire, faut que je retrouve l'algo d'origine, mais je suis certain qu'il marche, j'ai une démo pour le prouver !
Peut être aussi y a t'il une erreur dans ton implémentation ? File donc ton contre-exemple et de mon coté je vais vérifier ce que j'ai tapé.

http://www.chezmoicamarche.org/  
Code ( isN2InTab est une méthode qui repond true si un élément donné est présent plus de n/2 fois dansun tab ) :  

J'ai peut-être trouvé une autre méthode, faudrait juste vérifier que c'est bien en O(n) (à priori oui si j'ai bien compris) :
 
Je me suis dit que si un élément est présent plus de la moitié de la taille du tableau, alors on peut dire qu'un élément sur 2 est cet élément (qu'on peut appelé A). Evidemment si on pioche un élément sur 2 dans le tableau, on ne trouvera pas forcemment A. Il faut pour cela que A soit régulièrement réparti dans le tableau et dans ce cas-là, en découpant le tableau en couple d'éléments, on trouvera A dans chacun des couples.
 
Comment répartir A ? Comme définition d'une répartition, je me suis fixé qu'il ne fallait jamais que 2 éléments consécutifs soient identiques. En fait on va balayé le tableau de départ et on va vérifié si on peut ajouter l'élément en cours dans le tableau d'arrivée:
 

 
on va en fait empiler les éléments identiques jusqu'à avoir un élément différent qu'on va mettre dans le tableau résultat. À ce moment là, on va pouvoir vider un élément de la pile et le mettre dans le résultat. Et on continue ...
 
A-t-on besoin d'une pile ? Ce que je veux dire, c'est qu'on peut remarquer que les éléments de la pile seront toujours identiques :
imaginez une suite : A A B B
arrivé au premier B, on a A dans la pile (et A dans le résultat) ... évidemment si on passe tout de suite au 2eme B, ca posera problème mais en fait on va ajouter le premier B dans le résultat et on va donc pouvoir dépiler le A et ensuite mettre le B donc tant qu'il y a aura des éléments dans la pile, on pourra séparer tout les doublons.
Il suffit donc d'avoir 2 variables : une pour avoir la valeur des éléments dans la pile, et l'autre pour avoir la taille de cette pile.
 
C'est bien joli, mais sur l'exemple : B C D D D, cet algo va renvoyer la même chose.
Bah alors on va faire l'algo dans les 2 sens ! et là ça donnera D C D B D .
Je sais pas trop comment démontrer que ça marche à tout les coups (quand c'est faisable évidemment ... car si ya 4 D, on ne peut pas répartir correctement), j'ai fait des tests avec 100000 tableaux tirés aléatoirement de 10 éléments et je n'ai pas eu de problème (c'est à dire que quand il n'a pas pu répartir correctement, donc il s'est retrouvé avec au moins 2 fois le même élément à la fin du tableau, c'était quand il y avait trop d'un élément). je suis d'accord c'est pas une preuve.
 
Pour faire un image, faut s'imaginer des pièces placées au hasard sur un tapis. On forme une vague avec le tapis allant dans un sens et ainsi on va regrouper toutes les pièces d'un côté. Ensuite on reforme une vague dans l'autre sens, et là ça répartit régulièrement.
 
On a donc maintenant répartir les éléments du tableau.
- Une première remarque, si cette répartition échoue, donc si on se retrouve avec plusieurs fois le même élément à la fin du tableau, c'est que cet élément est présent plus de N/2 fois.
- Si la répartition fonctionne, les éléments qui pourraient être présent plus de N/2 fois sont soit le premier élément, soit le dernier du tableau réparti. Exemple :

On remarque que dans le cas d'un nombre impair d'élément, l'élément présent plus de N/2 fois (s'il existe) est en première et dernière position. De même si la répartition ne fonctionne pas, et ce quelquesoit la parité de la taille du tableau, l'élément A sera aussi en première et dernière position (sisi ... le premier tri ne marchera pas, donc des A seront groupés à la fin du tableau, et il y a aura forcement un A en première position lors du tri suivant ... mais aussi en dernière car le second tri ne marchera pas mieux).
On regroupe donc 2 cas dans un test : premier élément == dernier élément .
 
Si ce test échoue, on compte le nombre de fois qu'apparaît le premier élément et le dernier élément du tableau trié et si l'un des 2 est présent plus de N/2 fois, c'est bon, sinon il n'y a aucune solution.
 
Remarque : pour être plus rapide, au lieu de compter le nombre d'itération du premier et du dernier élément, on peut tout simplement lire 1 élément sur 2 du tableau (les indices impairs dans un premier temps) et si lors d'un balayage on trouve une valeur différente des autres, c'est que cet élément n'est pas présent plus de N/2 fois, on peut donc arrêter le balayage et passer au suivant (indices pairs).
 
En ce qui concerne la complexité ... cet algo balaye au plus 4 fois la tableau, et ce quelquesoit la taille de ce dernier, donc il me semble que ça ne dépend que de N (si j'ai bien compris le principe de complexité)
 
Pour exemple, voici en PHP la fonction qui répartit les éléments :
 

 
Ensuite pour trier un tableau, faut appeler cette fonction 2 fois en inversant le tableau entre temps :

 
Remarque : il me semble, dans la fonction de répartition, qu'on n'a pas besoin de vérifier si on peut dépiler un élément ou pas : si on arrive à ajouter un élément différent du précédent, il sera forcemment différent de la pile (sisi) et on pourra donc dépiler un élément. (biensûr faut tester si la pile n'est pas vide)
 
Cette solution est évidemment moins belle que celle proposée par tomlameche mais je la trouve plus abordable (peut-être parce que je vois plus facilement la démonstration) ... par contre en ce qui concerne de la pondre en 30 min (5pts de l'examen sur 2h) ...
 
Il doit y avoir une solution plus simple à trouver je pense !

 
j'ai edité mon msg, regarde le tableau avec lequel ca ne marche pas

 
algorithme: nb_occurences
 
donnees: tab_init: entier, tableau contenant les valeurs initiales
   N: entier, taille du tableau initial
 
variables: i: entier, indice de parcours du tableau initial
   j: entier, indice de parcours du tableau resultat
   end: entier, indice de la fin de la pile (= nombre de valeurs empilees moins 1 !)
   compteur: entier, compte le nombre d'occurences identiques
   tab_res: entier, tableau resultat "trie" de taille N
   tab_pile: entier, tableau utilise comme pile de taille N
 
constantes:
 
resultat: VRAI: booleen, le tableau initial contient au moins N/2 occurences egales
   FAUX: booleen, le tableau initial ne contient pas d'occurences presentent au moins N/2 fois

Voici enfin une solution sensee que Mr Tentacle en personne a trouve ! felicitation Mr Tentacle
 
En fait je me suis permis de le "mettre au propre" avec un algorithme (langage generique ) clair et présentable.
Je vais expliquer à ma façon comment marche cet algo, même si Tentacle l'a déjà expliqué à sa façon
 
/* le principe général : */
 

 
/* le fonctionnement */
 
Bon la rien à reprendre c'est le principe même de l'algorithme. Pour répartir uniformément les valeurs, on a besoin de 2 tableaux temporaires :
 
-un tableau nommé "resultat" qui contiendra les valeurs du tableau initial triées. J'entends (comme Tentacle ) par trié le tableau contenant les valeurs reparties uniformément de façon à ce qu'on est JAMAIS 2 cases consécutives du tableau résultat ayant la meme valeur...et non pas un tri rapide !
Cependant cette propriété sera fausse à partir de la ligne 32 (cf algo).
 
-un tableau nommé "pile" qui, non initialisé, se comportera comme une pile : il s'agit juste d'une file LIFO.
 
Un seul parcours du tableau initial ("tab_init" ) sera nécessaire et prouvera donc la complexité en O(N). (1 parcours de N)
 
1ere etape : on copie le tableau initial dans le tableau resultat (en fait c'est pas nécessaire, mais bon tant pis)
2eme etape : On parcours le tableau initial. Pour chaque valeur (que je nomme X):
   - si la case dernierement rempli dans tab_res (tableau resultat) a la meme valeur que X, on empile la valeur X     dans le tableau tab_pile (la pile)
   -sinon on regarde si la valeur a depiler est differente de la case dernierement rempli dans tab_res; si oui, on    privilegiera de mettre la valeur a dépiler dans tab_res au lieu de la valeur X (et on restera sur cette valeur     X pour la prochaine iteration). Si non, on met la valeur X dans tab_res (et on passe a la prochaine valeur X dans tab_init).
 
A l'issue de cette 2ème étape, on garanti que la valeur A (dont parle Tentacle) est uniformément répartie.
Par conséquent, si la valeur A est présente au moins N/2 fois, seuls (et oui SEULS) 3 cas de figure du tableau tab_res peuvent apparaitre :
 

 
On remarquera ceci : Si A est solution (presente au moins N/2 fois), soit A est presente en debut de tableau (dans le tableau resultat), soit en fin, soit en debut et en fin de tableau.
 
Cependant avec de tester ces valeurs, on doit proceder a l'etape suivante :
 
3eme etape : depiler la pile tant que possible et la copier a la fin du tableau resultat
 
4eme etape: On prend la 1ere valeur du tableau resultat et on regarde si elle est presente N/2 fois au moins.(2 parcours de N)
   On procede de meme avec la derniere valeur du tableau resultat (3 parcours de N)
 
Et c'est fini ! si la 4eme etape n'a pas retourner VRAI alors on retourne FAUX. Finalement cet algo est court et simple a implementer en soit...meme si j'en aurais jamais eu l'idee (ce qui est le plus dur pour un algo )
Cet algo aurait une complexite de 3*O(N) (parcours du tableau initial + verif de la 1ere valeur du tableau resultat + verif de la derniere valeur du tableau resultat) et une complexite memoire de 3*O(N) (dans mon exemple)...tout ceci reste donc tout a fait acceptable.
 
/* optimisation possible */
 
-la copie du tableau initial dans le tableau resultat ne sert a rien : copier juste la 1ere case de tab_init ds tab_res (amelioration en temps)
-Gerer la pile par une liste chainee (amelioration en memoire)
-la verification de la 1ere et derniere valeur peut etre plus rapide : (amelioration en temps)
 

 
bref avec une complexité en O(N), ce serai presque la complexité mémoire qui devient importante (au moins l'allocation d'un tableau énorme prend beaucoup de place et en plus est assez couteux en temps).
Ceci est donc une solution, meme si ce n'est pas la seule (enfin moi j'en vois pas d'autres ) , cet algo est le seul trouve jusqu'ici (qui m'a parfaitement convaincu )
 
Encore mes félicitations Mr Tentacle
 
PS : On vient de recevoir la note du DS : 7.6/20 de moyenne (promo de 68), j'ai eu 8.25/20...euh en fait non 8.25/10 (ben j'ai zapé cet exo, et un autre...qui etait qu'un pauvre tri rapide qu'en j'y pense ). Le major a eu quand meme "que" 14/20 (jsuis sur qu'il a perdu tout ses points a cet exo ...d'ailleurs a la fin de l'exam il était allé demande la solution a la prof )...Honnetement, vous auriez trouvé une telle solution (2 tableaux temporaires dont une pile) en 30 min ? :sarcastic (ca fait + d'un mois qu'on est sur ce topic )

Si ça marche, t'as oublié une partie de l'algo :

La partie en gras est là pour le cas particulier ou le nombre d'occurence est exactement égal à n/2 et qu'on a une répartition presque parfaite ( un élément sur 2 ). Si le nombre d'occurence est > n/2, y en a pas besoin.

 
j'ai recopier texto ton algo ! j'ai verifier suite a ton prog que t'a poste, c le meme algo (que j'a v ecrit en C) ... je veux bien reverifier une autre fois mais il me semble que je n'ai rien oublie !...jvé revoir ca
 
PS : deroule a la main avec cet exemple (c ce que j'ai fais) et tu verras que ca marche pas

Bon je déroule à la main avec A = 1,1,0,1,2,0,2,1,2,1
Je commence donc avec elt = 1, occ = 1
Etape 1 : A[2] = 1 = elt, donc occ = occ + 1 = 2
Etape 2 : A[3] = 0 <> elt -> occ = 1
Etape 3 : A[4] = 1 = elt -> occ = 2
Etape 4 : A[5] = 2 <> elt -> occ = 1
Etape 5 : A[6] = 0 <> elt -> occ = 0
Etape 6 : A[7] = 2 <> elt -> occ = -1 doncon change elt =2, occ = 1
Etape 7 : A[8] = 1 <> elt -> occ = 0
Etape 8 : A[9] = 2 = elt -> occ = 1
Etape 9 : A[10] = 1 <> elt -> occ = 0
On termine donc la boucle avec elt = 2.
On vérifie si 2 est présent n/2 fois : réponse : non
Taille(A) = 10, donc paire, on vérifie alors si A[10] est présent n/2 fois. A[10] = 1, présent 5 fois -> réponse true !
 
   
Je te confirme que tu as oublié  

Giz, il y a 2-3 trucs que je n'ai pas bien saisi dans l'algo que tu as posté :
- il me semble que tu ne passes l'algo de répartition qu'une unique fois alors que 2 sont nécéssaire et le 2ème s'appliquant sur le tableau inversé. Par exemple pour B C E D D, l'algo passé une unique fois va retourner la même chose, c'est pourquoi il faut inverser le tableau ( D D E C B) et refaire l'algo de tri ce qui donnera (D E D C B).
- effectivement je ne vois pas pourquoi tu copies le tableau de départ dans le tableau résultat
- pourquoi utilises-tu une pile sous forme d'un tableau, car comme je l'ai dit, les éléments dans cette pile seront toujours identiques
- De plus, je pense qu'il n'y a pas a vérifier si on doit dépiler un élément quand on a réussi à placer un élément différent du précédent : si on a empiler un élément X, cela signifie que l'element précédent est aussi X donc on a un tableau résultat ressemblant à ca 'A B X'. Si on arrive a ajouter un élément ... il sera forcemment différent de X, donc on pourra dépiler un X et on retombera dans le même cas que plus haut : A B X E X . Il faut bien entendu tester que la pile n'est pas vide.
 
Petite Question : Alors finalement ? c'était quoi la solution du prof ?  

 
Je vois pas où est le pb   , l'algo marche pareil. A la fin ma pile contiendra seulement le D. Je vide ma pile pour mettre le D a la suite du tableau resultat et je test valeur de fin/debut...puis pas present N/2 fois dc ca renvoi faux , c tout non    
 
L'histoire de la pile c vrai que t'a raison, comme les valeurs seront tjs les memes, on peut avoir 2 variables : la lettre et le nombre d'occurences de cette lettre dans la pile...c encore mieux effectivement.
 
Je ne suis pas encore allé voir la prof pour la solution
 
Tomlameche : OK ca marche , mais la solution de Tentacle reste plus comprehensible    

Remarque tu as raison en fait ... un seul passage suffit car même si les lettres ne seront pas correctement réparties, si il y a une lettre présente plus de N/2 fois, elle sera en première ou dernière place de toute façon.
En fait j'étais parti sur le fait qu'il fallait absolument répartir les lettres ... d'où le 2ème passage qui est nécéssaire dans ce cas précis ... bon par contre si tu fais les 2 passages, tu peux faire la petite optimisation dont j'avais parlé, c'est à dire lire une lettre sur deux et s'arrêter dès qu'on trouve une lettre différente (à la fin pour compter les occurences de la 1ere et dernière lettre).
De plus si au bout du 2ème passage, tu as 2 fois la même lettre en fin de tableau, tu es sûr et certain que cette lettre est présente plus de N/2 fois (donc pas de rebalayage à faire pour compter les occurences).
Reste à voir ce qui est le plus rapide ...
 
 
PS: je serais curieux de savoir la solution proposée par le prof en 30 min

 
T'inquiete, je vais lui demander ...elle parlait de partir d'un tri rapide (de toute façon c une aficionado des algo du type "divide and conquer"...elle connait rien d'autre   ). Avec un tri rapide, je ne vois pas comment elle peut obtenir un VERITABLE O(N) en complexité. Certes ca y tendra mais ca ne le sera pas. (dans ce cas la on peut autant dire que c du O(Nlog(N)))

Bon, alors elle a dit quoi, la prof ?

 
+1   Ce serait interressant de savoir ce qu'il fallait pondre en 30 min =)