Tri

Recherche :

Dernière réponse
Sujet : Tri
LeGreg	le tri a bulle c'est "j'oublie" :) A noter une variante du tri par insertion le tri shell ainsi que des methodes de tri utilisees regulierement comme QuickSort (consideree comme l'une des plus efficaces sur des listes quelconques) ou encore des particularites comme le tri radix, heritee de l'histoire de la mecanographie (trieuses mecaniques). LEGREG

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

LeGreg

le tri a bulle c'est "j'oublie" :)

A noter une variante du tri par insertion
le tri shell
ainsi que des methodes de tri
utilisees regulierement comme QuickSort
(consideree comme l'une des plus efficaces
sur des listes quelconques)
ou encore des particularites
comme le tri radix, heritee de l'histoire de
la mecanographie (trieuses mecaniques).

LEGREG

mogi

on peut améliorer le tri à bulle en positionnant un booléan qui sert à mémoriser si lors d'une passe on a fait une modification ou pas. si à la fin d'une passe on n'a fait aucune permutation alors le tri est terminé.

vec=vecteur contenant toutes les valeur a trier
i=longueur(vec)
test=vrai
tant que i>0 et test
faire
test=faux
pour j,1->i-1,j=j+1
faire
si vec[j]>vec[j+1]
alors
permuter vec[j] et vec[j+1]
test=vrai
fsi
fin boucle
i=i-1
fin boucle

question : tri par extraction = tri par insertion ?

parce que ce vous donnez comme code, pour moi, c'est le tri par insertion :)

kangol_from_PPC

voici 2 algo en pseudo code pour ces methode de tri :

tri a bulle :
--------------
vec=vecteur contenant toutes les valeur a trier
i=longueur(vec)
tant que i>0
faire
pour j,1->i-1,j=j+1
faire
si vec[j]>vec[j+1]
alors
permuter vec[j] et vec[j+1]
fin boucle
i=i-1
fin boucle

--------------------------------------------------------
tri par extraction simple:
--------------------------

vec=vecteur contenant toutes les valeur a trier
len=longueur(vec)
x=1
tant que x<=(len-1)
faire
i=x+1
tant que i<=len
faire
si vec[i]<vec[x]
alors
permuter vec[i] et vec[x]
i=i+1
fin boucle
x=x+1
fin boucle
--------------------------------------------------

voila ! ;)

kangol_from_PPC

le tri par extraction simple c presque la meme chose mais ds le sens contrtaire! je m'explique :

soit une liste de nbr : 60 15 7 8

on compare 60 et 7
on regarde le + petit et on le met en 1er lieu

=> (je compaer les chiffre souligner puis je les inverse si le faut)
7 60 15 8
7 60 15 8

ici on sait deja ke 7 est le plus petit => on y touch + !

7 60 15 8
7 15 60 8

15 est le plus petit des nbr non triés !
7 8 60 15

=> version finale : 7 8 15 60

[edtdd]--Message édité par kangol_from_PPC--[/edtdd]

LetoII

bon alors le tri à bule voilà le principe:

imagine un tableau:

5 8 4 9 2

tu voudrai le trier, la méthode consiste à faire remonter l'élément le plus petit du tableau (ou le plus grand) vers ça place, comme une bulle, par des passes successives, ce qui donne sur l'exemple:

passe 1:

5 8 4 9 2
on compare 5 et 8, 5 < 8 donc on touche pas
on compare ensuite 8 et 4, 4 < 8 donc on interverti:

5 4 8 9 2

on compare 8 et 9, pas de changement

on compare 9 et 2, 2 < 9 donc:

5 4 8 2 9

9 a ateind ça place on ne le comparera plus pour gagner du temps (en fait à chaque passe le plus gros se retrouve à la fin)

passe 2:

4 < 5: 4 5 8 2 9
5 < 8: pas de changement
2 < 8: 4 5 2 8 9

on a fini pour cette passe

passe 3:

4 < 5: pas de changement
2 < 5: 4 2 5 8 9

fini

passe 4:

2 < 4: 2 4 5 8 9

fini

passe 5:

plus de changement à faire le tri est fini

le tri par extraction je me souvient plus

magot

Qu'est ce que le tri a bulle et le tri par extraction??