Quel est l'algorithme qui a vous a épaté par sa puissance, ou qui vous a donné du fil à retordre pour le comprendre, ou tout simplement parce que c'est votre préféré ?

Joce !

Je suis un fan du VQ

MagicSort m'a laissé sur le c*l
 
algo pourtant très simple, mais thérorie derrière à devenir chèvre

 
c'est kwoaaaaaaaaaaa ?

 
un algo de tri

je m'en doute, mais ça consiste en kwoi comme tri, j'ai boulayé avec google pas trouvé ?

puisqu'on en parle, la transformée de fourier justement, même si c'est pas vraiment un algo !  

Ben oui c'est MagicBuzz qui l'a pondu un soir de fiesta.
Il a toujours pas réussi à comprendre ce qu'il avait écrit.

Ca m'est déjà arrivé
 
Sinon, si qq1 pouvait retrouver cet algo justement...
Parceque je sais plus du tous où je l'avais trouvé.
 
 
Sinon, pour résumer, J'avais un tableau de 200 000 lignes en VB *sic* que je devais trier.
 
Avec un algo de tri genre tri à bulle, ct même pas la peine, je pouvais fumer un paquet de cloppe avant que ça termine.
 
Avec QuickSort, ça mettait plus de 15 minutes.
 
Avec MagicSort ben... Même pas une minute.
 
En fait, MagicSort, quand on tombe bien dans le bon cas (il faut que le nombre de lignes soit suppérieur à l'intervalle entre la plus petite valeur et la plus grande, pour rentrer dans le cas où ça bombarde) il éclate QuickSort d'une force monstrueuse.
 
En fait, il parcourt 1 fois et demi ton tableau, un point c'est tout (quand on est dans le bon cas, si les valeurs sont trop dispersées, c'est pire que le tri à bulle)
 
J'avais trouvé un site ou l'algo était bien expliqué, mais j'ai relu une dizaine de vois, puis je me suis contenté de transcrire le code C en VB pour mes besoin sans chercher à comprendre plus Tout ce que je sais, c'est que comme le tutorial disait "It's like Magic !"

ton histoire ressemble beaucoup a une vieille legende ... pas de traces sur le web, ni dans les bouquins d'algos, juste quelques rumeurs ..
 
non pas que je sois dubitatif ... mais plutot curieux.

 
y'a des algos de tri qui n'effectuent aucune comparaison

genre le tri compteur je croa non ?

http://codercorner.com/RadixSortRevisited.htm

le tri compteur ou par comptage, non, mais le tri a vec l'algo de la "trieuse", aucune comparaison
 
edit: à moi que je confonde compteur et tri par position

le truc c'est que les éléments dans la liste
sont déjà triés (pas besoin de connaitre l'ordre
relatif des élements lorsqu'on connait l'ordre absolu).
 
tri des mécanographes -> la machine n'interprète pas
la valeur des bits mais place les cartes dans le bon  
chemin parce que tout est cablé.
 
LeGreg

Une très bonne page pour vois les différents algos de tri :
 
http://www.cs.ubc.ca/spider/harris [...] -demo.html
 
Sinon, ouais, vu la rapidité et la méthode, ce que j'avais trouvé sour le nom de "MagicSort" semble être le "RadixSort"

Sinon, pour les tris débiles, j'en avais trouvé un très rapide que j'avais fais qui imposait la même limitation que ce "MagicSort", pour les tris entiers.
 
Il fallait connaître le min et le max de l'intervalle.
Il fallait que ces la diff entre ces deux nombre soit inférieure à la taille du tableau (afin d'éviter des pertes de place mémoire trop importante) et ça n'était pas applicable aux très gros tableaux (sinon, a plus de place en RAM )
 
Source en VB du tri ensuite :
 
for i = lbound(tabOri) to ubound(tabTmp)
   tabTmp(tabOri(i)) = tabTmp(tabOri(i)) + 1
next
 
j = lbound(tabTmp)
for i = lbound(tabOri), ubound(tabTmp)
   do while j < ubound(tabTmp) and tabTmp(j) = 0
     j = j + 1
   loop
   tabOri(i) = j
   tabTmp(j) = tabTmp(j) - 1
next
 
Et hop ! Le tableau trié en 1 passage + (min - max) / nblignes

La possibilite de tout cabler est à la fois une propriété
intéressante des machines électronique et à la fois
une chose dont on s'éloigne sur les machines actuelles
parce que une machine qui fait qu'une seule chose même si elle le fait trés bien est le plus souvent trop coûteuse a mettre en oeuvre. Et les économies que l'on fait le sont sur les grandes échelles.
 
On observe un processus similaire avec le code qui s'automodifie.
Aucun doute qu'on obtiendrait une performance optimale dans tous les cas de figure avec du code qui s'automodifierait pour accélérer les sections critiques (en vitesse).
Pourtant j'observe très peu de code automodifié en regardant autour de moi ou alors ils le sont de façon très codifié, très limité (chargement de librairies dynamiques, choix des optimisations au lancement etc..).
Pourquoi? a mon avis parce qu'ils sont impossibles à maintenir et surtout parce que ces économies d'échelles permettent d'envisager dans le temps qu'il faudrait pour mettre en oeuvre ces techniques et sans la douleur pour les maintenir, un matériel qui rendra obsolète cette recherche de performance (déplacement du goulot d'étranglement).
 
LeGreg

les algo de cryptage sont assez balez aussi
Chiffrement Vigenàre
Enigma
DES
RSA
PGP
pour ne citer ke ceula...

crypto évidememnt (en terme de chiffre dépense dans la recherche d'algorithmes fondamentaux).
 
Je voudrais aussi citer le sequençage des génomes qui etait fut un temps (l'est-il encore?) un moteur pour toute la recherche avançée sur le traîtement des chaînes. (pattern matching, suffix trees).
 
Legreg

Il ya effectivement de beaux algo dans la recherche et comparaison de sequences biologiques (Blast pour le plus connu). Il s'agit en general de methode heuristiques associant pas mal de techniques entre elles (hash, recherche de scores dans une matrices suivant des processus plus ou moins compliques, chaines de markov, etc...). J'avais aussi ete bluffe par un algo de randomization (merlenne twister si mes souvenirs sont bons).
 
Il y a aussi une classe elegante: les algorithmes genetiques.

un qui m'a hachement impressionne c'est le test de primalite en temps polynomial, il est pas tres vieux en plus, je sais plus ou j'avais vu ca... en plus, l'algo tiens en moins de 10 lignes, c'etait monstrueux

on a implementer vignenere en cours cette année, alors ou il y ades subtilités que j'ai pas vues, ou c'est l'algo l plus pourri que je connaisse ...

Il y a un fort joli algorithme de résolution de système linéaire, avec une belle théorie et des résultats de performance bien supérieurs aux autres dans la plupart des cas : le GMRES.
Bon évidement, c'est très mathématques et je doute que la plupart des codeurs fous en ai besoin un jour, mais si vous faites du calcul numérique, vous devez le connaitre.

 
je connais mais c est pas le plus baleze :
 
resolution directed un systeme lineaire par une methode multifrontale c est mucho + complique à comprendre
 
Enfin je suis d accord avec toi les algos les plus balezes sont en maths appliquees !!!

Hello tout le monde,
 
Etant assez débutant dans le domaine, je suis toujours ébahi devant des mécanismes aussi simples que le parcours largeur ou profondeur d'un graphe à l'aide respectivement une file et une pile, ou des "astuces" du type schéma de Hörner ou méthode de Karatsuba pour la multiplication. Toutes ces "petites" choses me font bien triper =)
 
A+

Pour moi, les algos sont comme les formules en math ou en physique : les plus balèzes sont ceux qui sont à la fois d'une simplicité désarmante et d'une puissance ahurissante (je pense par exemple, en physique, à la célèbre relation entre masse et énergie énoncée par Einstein).

Perso, c'etait un algo de verification dans un multi-graphe orienté...
Pour ceux a qui ca dit quelque-chose, c'etait un mélange entre parcours prioritairement en largeur, calcul des composantes fortement connexes, et je sais plus trop quoi...
 
Le genre d'algo qui en maths est déjà assez compliqué, faut penser à tous les cas limites, et quand on veut le transcrire en C là on est vraiment dans la merde.
 

le tri à bulle (2 semaines d'algo inside)
ah si sinon en sup on avait fait avec maple un prog de criptage avec les nombres premiers : c t très sympha

Euh... MDR.
 
Un programme qui affiche les puissances de 0 à I d'un nombre X
 
http://forum.hardware.fr/forum2.ph [...] h=&subcat=

la fonction d'ackermann, je pense est une bon exemple d'algo bien relou...
sinon en 3d, ya les algos de Decasteljau, Béziers, voir même bresenheim, qui sont vraiment relou a implémenter ...(genre de casteljau, 4 ou 5 for imbriqué ...)

moi j'ai pas d'algo en tete, mais la formule de Gauss qui donne la somme des n premiers entiers, pour rappel n(n+1)/2 m'a bien marqué ! D'après l'histoire, il l'a trouvé a 5 ans quand son prof lui avait donné une addition a la con pour l'occuper parce qu'il s'emmerder en cours    
 
Le petit gauss s'est alors rendu compte qu'en ecrivant la somme deux fois mais en ordre inverse, on obtenait toujours le meme nombre en sommant verticalement :
 

ouai c clair Gauss powaaaaaaaaaaaaaa.

 
Ca me rappelle Niels Bohr (physicien). Pendant un oral on lui demande "Comment mesurer la hauteur d'un immeuble avec un barometere ?" Et lui de repondre... On monte en haut de l'immeuble, on laisse tomber le baro et on mesure le temps qu'il met pour arriver en bas
 
Sinon je suis assez fier de mon algo d'ecriture XML avec gestion des tags ouverts/fermes

 
il créé un tableau de meme dimension en plus, pour ranger ?

les algo de tri normo sont en n*log(n) non?