Voila un petit challenge histoire de présenter un algo de tri que peu connaissent et qui est ... a mon avis le plus rapide possible.
Il a un énorme inconvénient : il ne permet de trier que des nombres entiers de 1 ou 2 octets ...
En fait, ce qui importe, c'est la différence entre le plus petit et le plus grand de ces nombres, qui ne doit pas être trop importante (quelques milliers, voire millions).
Ce tri est fabuleux : sa complexité est ... linéaire !
Pour les non initié, ca veut dire que trier un tableau de 100 nombres prendra 10 fois plus de temps que pour un tableau de 10 nombres ... du jamais vu pour un algo de tri.
Il est très très rapide : il trie un tableau en, aller, 2 passes. Encore que le plus gros du travail est fait en une passe. Un passe = une itération du début à la fin ...
Alors, vous avez une idée à quoi cela ressemble cet algo ?

le bon vieux radix des familles ...
 
>> Il a un énorme inconvénient : il ne permet de trier que des nombres entiers de 1 ou 2 octets ...  
 
non, ça permet de trier n'importe quel nombre entier / réel. le petit challenge : trouver comment avec google.

Tu m'as fait peur toi avec ta réponse en moins de 10 minutes.
Je connaissais pas le tri radix, et ce que j'ai pu en voir (http://www.stcommunications.ca/~mboisso/Algo/triselse.shtml), ben c'est pas ca.
Cet algo est encore bien plus rapide, et je persiste, ne fonctionne qu'avec des entiers, négatifs ou pas (apparement c'est pas le cas du radix).
Pa smoins de 3 for(; imbriqués pour le radix, il n'y a que 2 fro(; non imbriqués (à la suite) pour cet algo mystérieux ...

Oups, j'ai pas compté le for de affecter(...) ... 4 for(; imbriqués pour le radix ...

tu es tombé sur une implémentation à 2f.
 
http://codercorner.com/RadixSortRevisited.htm
http://www.stereopsis.com/radix.html

Ca vaut pas le bogotri

 
Mouai, c'est a peu pres ca. Voila ma variante (que je préfère ) que je connais sous le nom de "tri compteur"
 

 
SortedBuffer[i] = nombre d'occurences de cette valeur
Par exemple, si SortedBuffer vaut { 2, 0, 1, 3} on reconstitue le tableau trié ainsi : 0 0 2 3 3 3
(2 * 0, 0 * 1, 1 * 2, 3 * 3, ...)  
 
Je suis un peu déçu de mon coup là. Mais bon j'ai obtenu de la doc sur comment appliquer ce tri aux réels ...

Sa bouffe de la memoir, ca ....
256 entier pour classer 4 entiers.
et on parle pas de flottant dur 4 octets....
Et en plus tu ne parle même pas de la passe à faire pour reconstituer le tableau dans l'ordre.
 
Le radix, ca c'est de l'algo robuste.

Ca bouffe de la mémoire ? !!!!
 
Aucune copie du tableau n'est nécessaire. Seul un tableau de 256 integers est nécessaire pour trier un tableau de char.
Que ce dernier fasse 1 octet ou 1 Go, mon tableau de 256 integer me suffit ...  
La ou c'est moins rose, c'est pour trier des short. Il faut un tableau de ... 65536 integers ... mais ca reste a mon sens raisonnable. 256 Ko de mémoire aujourd'hui ca passe ...
Par contre, trier des long ... je vais attendre d'avoir 4 Go de RAM
 
Bon j'avoue, 3 passes :
- initialisation du tableau de taille 256 à 0 (je l'avais oubliée, pas la mort)
- parcours du tableau à trier ... 1 à 4 milliards d'itérations
- parcours du tableau de 256, en ecrivant Tab[i] fois chaque valeur dans le tableau qui était à trier ... 1 à 4 milliards d'itérations
 
Ca y est, c'est trié.
 
Au fait,

est tiré d'une implémentation du radix ...
Et je vois pas en quoi c'est plus robuste.
 
kadreg > C'est quoi le bogotri ? Apparement un algo qui tri de manière aléatoire une petite suite ...

qsort ?    
ok je sors

Ca bouffe de la mémoire.
Moi avec un quick sort j'utilise pas un tableau de 256 entier
 
Pour trier 50 octets en qsort tu n'as pas besoin de 256*4 octect, mais plutôt 50 autres entiers.
 
Les cas d'utilisation de ton algo (connu) sont très rare,
 puisque si tu veux rataché un objet au chiffre, la tu souffres encore plus de ce problème de mémoire.
On utilise ton algo sans même penser que c'est un trie dans les cas ou tu peut l'utiliser, généralement.
 
Le radix en efficacité sera proche de ton algo,
tu pourras trier n'importe quel type de valeur (avec des astuces)
sans te soucier du type de la valeur.
 
Par exemple si tu as des mots à mettre dans le bonne ordre -> explosion de ton algo en mémoire.

 
du jamais vu? ou tu as vu ca toi?
surtout pour trier 100 nombres de 1 octet
devoir initialiser un tableau de 256 octets c'est vraiment cool
De plus pour trier des longs avec ton algo tu n'as pas besoin de 4Go de memoire mais plus raisonnablement simplement 4 * 256 octets.. (par contre il faut faire 4 passes au lieu d'une)
 
LEGREG

c'est ce qu'on appelle un flop

c'est pas ca qu'on appelle un tri spectral ?
 
 
 
et point de vue complexité c'est uniquement UNE passe, parce que si tu tries vraiment qqchose et pas juste 3 chiffres qui se battent en duel, ca fais que n passage, les autres sont négligeables
 
mais vu les cas d'utilisation tellement restreint, il ne sert à rien.
 
ce tri peut venir à l'esprit lorsqu'on est en face du probleme : comment savoir quel entier revient le plus souvent dans une liste
 
d'ailleurs, si les valeurs des entiers sont très distribuéees, comment résoudre le problème facilement ?
liste chainée et hachage ?
 
y a mieux ?

legreg
si t'arrive à utiliser sont algo en 4 passe pour des long avec
 4 * 256 octets, t'es fort.

Vous avez vite lu c'est pas possible ...
 

 
Et pour trier 500000 octets en qsort in t'en faut ... 500000 autres ...
PAS avec cet algo ou tes 256 * 4 suffisent (*4 c'est moi qui le dit, c'est par précaution, mais ca peut etre 256*1 pour un tableau < 256, 256 * 2 si < 65536 ...)
 
 

 
ben en qsort par exemple, trier 1000 nombres n'est pas 10 fois plus lent que pour 100 ... c'est exponentiel, comme pour tous les algos capables de trier une grande suite de nombres.
Et malgré qu'il faille initialiser un tableau de 256 octets (100 nombres ... moi je tableai splutot pour 10000 ...), l'algo reste BIEN plus rapide ET facile a mettre en oeuvre que le tri bulle par exemple
 

 
Je crois pas avoir dit le contraire ... sauf que je sais pas où est cette 4° phase ...
 
Moi je le trouvais intéressant à étudier. Je suis tout à fait d'accord que c'est presque impossible à utliser dans la vraie vie, mais n'empêche ca existe un algo de la mort qui tue pour trier 4 milliards d'octets en à peine plus du double d'opération + 1 Ko de RAM bouffée seulement + une facilité déconcertante à mettre en oeuvre ...

"500000 octets en qsort in t'en faut ... 500000 autres ... "
ou c'est que t'a vu ca.
le trie rapide est en moyenne n(log n) et pas exponentiel (et ca change tout).
et je ne parle pas du radix.
 
L'avantage c'est que tu peux utiliser le même tableau.
alors que toi tu as déja oublié la passe qui consiste à reconstituer le tableau...
 
 
C'est pas un trie c'est un calcul du nombre d'occurence,
 ce qui n'est pas totalement la même chose.
Si t'as besoin de lier cette valeur avec autre chose (90% des cas d'utilisation d'un trie),
t'es dans la merde.
 
Ton truc ca sert à rien à part faire des stats
, alors au lieu de perdre du temps passe à autre chose...
 
J'utilise ton trie depuis 10 ans (je l'ai 3 fois rien que dans l'algo que je suis en train de faire sur les vertices)
et je n'appel pas ca un trie parce que ce n'est pas un trie, c'est tout.

 
bon ce qui precede prouve juste que tu es a la rue en algo..
le temps d'execution du tri quicksort est dans le pire des cas en theta de n^2 (n*n) ce qui est carré (polynomial) et non pas exponentiel. Ceci dit c'est tres mauvais pour un algorithme de tri. Ce qui le sauve c'est qu'en moyenne (sur tous les cas), il prendra un temps en n*log(n).
Evidemment on estime le cout d'une comparaison a un cout moyen constant qui ne dépend pas du nombre d'éléments dans la liste a trier. Et surtout on ne limite pas les valeurs prises par les elements a trier (ce qui est fait dans le tri compteur ou tri a histogramme ou spectral ou ce que vous voulez comme nom).
 

100 nombres, je ne fais que reprendre tes chiffres .
 

 
De toute facon personne n'utilise le tri bulle .
 
Ceci dit, qsort est dans la stdlib C,  
sort est dans la stdlib C++,  
et l'algo que tu décris est déjà connu  
et utile (je l'utilise ou l'une de ces variantes
dans un de mes projets persos) mais je voudrais juste que tu relativises tes propos.
 

 
je reagissais juste sur le fait que tu avais besoin de 4Go pour trier des long. Excuse moi si j'ai mal interpreté ce que tu disais.
 

 
Recalcule la place mémoire prise.
Certaines variantes du quicksort le font dans le tableau
d'origine, l'algo avec histogramme a besoin pour reconstituer la liste triee d'un tableau de taille au moins equivalente.
(ou alors tu es limité a un seul histogramme en bidouillant un peu, donc plutot inutile pour des entiers de plus de 16 bits)
 
LEGREG

Bon tout d'abord calmons nous, je trouve le ton de ce post inutilement houleux.
Ensuite, soyons clairs, car apparement je me suis mal exprimé :
Cet algo se base sur la fréquence d'apparition des éléments d'un tableau pour le trier. C'est cela que je trouve astucieux, et non pas la manière dont est recherchée la fréquence des nombres.
 
Freq[ Tab[i] ]++;
 
Oui ça je suis d'accord c'est connu, utilisé par beaucoup depuis longtemps. Mais ça ce n'est que la moitié de l'algo, la moitié qui fait que Hercule considère que ce n'est pas un algo de tri mais un algo de statistiques.
Il n'empêche qu'en entrée je fourni un tableau d'entiers et que en sortie celui-ci est trié. Moi c'est ce que j'appelle un algo de tri.
Cet algo est exotique car il ne manipule pas les éléments triés, il les compte, d'où son nom de tri compteur.
Or dans la grande majorité des cas de tri, on ne tri pas des nombres pour le plaisir mais on tri des éléments en fonction d'une de leur caractéristique. Cet algo ne permet pas de faire cela (on ne peut pas par exemple trier une liste de personnes en fonction de leur age ... bien que ce soit des entiers short en plus) et a donc très peu d'utilités. Mais il peut en avoir une un jour pour quelqu'un ...
"Comment obtenir les 10 plus grands nombres d'une liste de 100000 ..." fiout, un petit tour de passe-passe et voila ma liste triée. Un des cas possibles cité par Feanor.
 
Alors je le donne en entier sous forme d'une fonction exploitable :
 

 
J'ai recherché la simplicité, pour être compréhensible par tous.
 
Bon, après les citations ...
 

 
J'utilise ton trie depuis 10 ans (je l'ai 3 fois rien que dans l'algo que je  
 
suis en train de faire sur les vertices)
et je n'appel pas ca un trie parce que ce n'est pas un trie, c'est tout.[/quote]
 
Je te rassure, j'ai pas passé 10 ans sur cet algo, juste 10 minutes, puis je suis passé à autre chose ...
Et j'ai jamais dit que mon truc "servait à quelque chose". Mais je pense que ça a plus d'utilité que de calculer les décimales de Pi et ca y'en a qui y passent bcp de temps ...  
 

 
vi vi c'est une boulette ... j'ai pas réfléchi suite à la lecture de ceci :
 

Du coup j'ai pas compris ce que tu as voulu dire ...
 

 
Exponentiel, j'ai dit ca au sens de "quelque chose qui croit de manière élevée", pas au sens mathématique. Bon c'est vrai que les 2 courbes n'ont pas la même gueule, mais j'avais à l'esprit d'être compris (tout le monde n'a pas étudié la complexité algorithmique ici ...) et je t'avoue que si ne pas savoir par coeur que le qsort est au max en theta de n^2 (n*n) mais en réalité plus proche de n*log(n), alors oui je suis à la rue.
 

 
c'est tout calculé ... un élément peut apparaître 4 milliards de fois ... un long pour stocker la fréquence d'un élément ... 256 éléments ... 256 * 4 = 1Ko.
Avec un tableau de 1Ko, on peut trier un tableau de 4 milliards d'octets ... et tres  
 
rapidement ... en grosso modo 8 milliards d'operations (affectations).
le qsort ... log(4 milliards) = 22 en étant gentil. Le Qsort y'a au bas mot un echange par opération, et ca ça coute plus q'une affectation ... Dans le meilleur des cas, le qsort est 10 fois plus lents.
Apres je te suis pas ... pas besoin d'un tableau de taille equivalente ni de bidouille. Une fois l'histogramme de fait, le tableau source on en a plus besoin ...  
on l'écrase avec sa version triée...

t'as pas essaye avec l'algo de "dijtra "
ca c la phonétique ..pour l'ecriture suis complètement largué

je ressors ce vieux thread pour faire de l'explication de texte:
 
On vous a toujours dit qu'un tri par comparaison demandait en moyenne un temps en Theta(nlogn).
Or on a sorti un tri qui s'execute tout le temps en Theta(n) meme dans le cas le pire. Comment est-ce possible?
 
Le tri par comparaison s'appuie sur une relation d'ordre
("plus petit que" ). En l'absence de plus de precision, pour ordonner un ensemble d'elements n, (ordonner consistant a transformer un ensemble d'elements en une suite où deux elements successifs verifient la relation "plus petit que" ) vous devrez effectuer "en moyenne" un Theta(nlogn) operations (comparaisons par la relation d'ordre) ceci quel que soit le type d'elements a trier et quel que soit l'algorithme que vous utilisez.
 
Bien entendu cela est tres general et ne tient pas compte des spécificités des objets a trier. Par exemple, quand on est prof il est bien connu que le meilleur moyen de trier un paquet de copies (notés de 1 a 20) est de faire 20 tas avec les copies, et de prendre les copies une a une et de les placer sur leur tas correspondant. En comptant le temps nécessaire pour rassembler les tas de copies, on arrive a un paquet de copies trie en temps lineaire.
 
cela est generalisable pour tout ensemble d'objets prenant un nombre connu et limité de valeurs.
Ainsi si on a des objets qui ont des propriétés "couleur"  
sous forme de chaine "rouge", "bleu", "vert", "violet"
et que l'on veut ordonner suivant la loi suivante: rouge < vert < bleu < violet.
Plutot que d'utiliser une relation d'ordre derivée de cette loi, on va simplement
construire un "histogramme" comptant les objets suivant les valeurs de leur propriété couleur.
Apres une premiere passe (temps lineaire) => on a nbRouge = x, nbVert =y etc...
Ainsi une deuxieme passe (temps lineaire) permettra de deplacer les objets dans un  
nouveau tableau en les regroupant par couleur.
 
En fait tout le ressort de la methode repose sur le fait que les valeurs prises
par les objets sont deja triees et qu'elles sont en nombre limité.
 
Quelles sont les limites de cette methode?
La methode ne fonctionne bien que si le nombre de valeurs  
a prendre en compte dans l'histogramme n'est pas *tres grand* devant le nombre
d'objets a trier.
Exemple: pour trier des chaines de caracteres de longueur arbitraire
ca ne marche pas. Le nombre de valeurs differentes qu'il faudrait mettre dans l'histogramme
peut etre énorme (voire infini) par rapport au nombre d'elements à trier en réalité, et l'on perd tout
intérêt du tri linéaire.
Ou pour trier un petit nombre d'entiers prenant des valeurs sur 32 ou 64 bits,  
le coût des passes, de l'histogramme etc peut etre nul par rapport a un tri qui peut etre effectué
sur place en temps nlogn (independamment du nombre de valeurs prises par les objets).
 
Je parle d'histogramme mais cela vaut également pour tout tri linéaire qui serait basé sur
le même principe (valeurs triées à l'avance en nombre connu et limité).
 
Voila j'espere que ca aura clarifié un peu ces histoires de tri.
 
LeGreg