hg S’enregistrer Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie

Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie  forum informatique Tunisie Index du Forum

hg Bac Tunisie Algorithmique et programmation TIC réseaux php javascript sql access activités programmation c
hg
FAQ FAQ Rechercher Rechercher Membres Membres Groupes Groupes Profil Profil Se connecter pour vérifier ses messages privés Messages Privés Connexion Connexion


 Forum de l'excellence et l'excellence en innovation 
Pour participer à notre Forum, vous devez
 
inscrire sur notre forum a partir d'ici
 
  NB :
Les membres ''zéro messages'' seront supprimés automatiquement après un nombre de jours donné !!!!
             
   
 
  
forum d'aide informatique : internet, réseau, programmation informatique ...
Tri shell
 
 
Poster un nouveau sujet   Répondre au sujet    Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie Index du Forum -> Algorithmique & programmation -> Algorithmes de tri
hg Sujet précédent :: Sujet suivant   hd
Auteur Message
ibrahim1


Hors ligne

Inscrit le: 14 Fév 2009
Messages: 2
Masculin
Point(s): 9
Moyenne de points: 0

Posté le: Dim 24 Jan - 17:48 (2010)    Sujet du message: Tri shell Répondre en citant

PublicitéSupprimer les publicités ?
Tri Shell
Ce tri consiste à trier séparément des sous-tableaux du tableau initial objet du tri, formés par les éléments répartis de p éléments.
à Le tri shell est une amélioration du tri par insertion. Au lieu de faire une rotation de tous les éléments, nous ferons une rotation par pas de p ce qui permet d’affiner le tri du tableau et de faire moins de déplacements d’éléments.
Nous commençons donc par un pas assez élevé et nous le diminuons au fur et à mesure jusqu’à arriver à un pas de 1. Le pas est diminué à l’aide d’une suite, mais il faut construire cette suite de manière à ce que les valeurs ne soient pas multiples entre elles sinon nous allons traiter des éléments et pas d’autres.
Shell propose la suite d’incréments vérifiant p1=1, pn+1 =3pn +1 en réalisant les tris du grand incrément possible vers le plus petit.
D’autre par, puisque au dernier stade, p0 est égale à 1, nous déterminerons le pas maximal par récurrence en inversant la relation donnée ci-dessus :
                        Pn+1 =3pn +1
Et en s’assurant qu’il y a encore un nombre suffisant de composantes dans les sous vecteurs considérés.
Remarque :
Le tri shell trie chaque liste d’éléments séparés de p positions chacun avec le tri par insertion. L’algorithme effectue plusieurs fois cette opération en diminuant p jusqu’à p égal à 1 ce qui équivaut à trier tous les éléments ensemble.
Exemple 1 : grandeurs successives de p pour n=100 Calcul du plus grande valeur de p tel que p<100 :
U0=0
U1=3U0+1=1
U2=3U1+1=4
U3=3U2+1=13
U4=3U3+1=40
U5=3U4+1=121  

Conclusion: la plus grande valeur de p tel que p<100 est 40. Les valeurs successives du pas p seront alors : (ou la division par 3 est une division entière.
p1=121/3=40
p2=p1/3=40/3=13
p3=p2/3=13/3=4
p4=p3/3=4/3=1  

Exemple :
Evolution du tableau au fil du tri shell. Le pas, représenté en rouge est également indiqué ainsi que la valeur en mémoire, sur laquelle porte la comparaison. En bleu, les valeurs sur lesquels portent les comparaisons à chaque étape.
 
Tableau  
Memoire  
Pas  
Commentaire  
6  
3  
0  
9  
1  
7  
8  
2  
5  
4  
t(5)=1  
4  
Comparaison de memoire=t(5) avec t(1) : t(5) reçoit t(1) puis t(1) reçoit memoire  
1  
3  
0  
9  
6  
7  
8  
2  
5  
4  
t(6)=7  
4  
Comparaison de memoire=t(6) avec t(2) : pas d'échange  
1  
3  
0  
9  
6  
7  
8  
2  
5  
4  
t(7)=8  
4  
Comparaison de memoire=t(7) avec t(3) : pas d'échange  
1  
3  
0  
9  
6  
7  
8  
2  
5  
4  
t(8)=9  
4  
Comparaison de memoire=t(8) avec t(4) : t(8) reçoit t(4) puis t(4) reçoit memoire  
1  
3  
0  
2  
6  
7  
8  
9  
5  
4  
t(9)=5  
4  
Comparaison de memoire=t(9) avec t(5) : t(9) reçoit t(5)  
1  
3  
0  
2  
6  
7  
8  
9  
6  
4  
t(9)=5  
4  
Comparaison de memoire avec t(1) : pas d'échange t(5) reçoit memoire  
1  
3  
0  
2  
5  
7  
8  
9  
6  
4  
t(10)=4  
4  
Comparaison de memoire=t(10) avec t(6) : t(10) reçoit t(6)  
1  
3  
0  
2  
5  
7  
8  
9  
6  
7  
4  
4  
Comparaison de memoire avec t(2) : pas d'échange, t(6) reçoit memoire  
1  
3  
0  
2  
5  
4  
8  
9  
6  
7  
4  
1  
A ce stade, le pas diminue 4/3 donne un pas de 1  
A ce stade, le tri Shell revient à effectuer le tri par insertion. L'exemple s'arrêtera donc ici. Il faut cependant remarquer que, grâce aux différentes étapes du tri Shell, le tableau est un peu mieux organisé : La moyenne des valeurs de la première moitié du tableau a diminué. Ce résultat est d'autant plus remarquable que le tableau à trier soit grand.


 
Revenir en haut
Visiter le site web du posteur
KARIMOS
Administrateur

Hors ligne

Inscrit le: 02 Nov 2008
Messages: 1 710
Masculin
Point(s): 5 479
Moyenne de points: 0

Posté le: Dim 24 Jan - 22:05 (2010)    Sujet du message: Tri shell Répondre en citant

excellent preparation merci pour le partage  Okay

 
Revenir en haut
Contenu Sponsorisé






Posté le: Aujourd’hui à 17:01 (2016)    Sujet du message: Tri shell

 
Revenir en haut
Montrer les messages depuis:   
bg bd
Poster un nouveau sujet   Répondre au sujet    Bac Tunisie Algorithmique et programmation : BAC INFORMATIQUE En Tunisie forum informatique Tunisie Index du Forum -> Algorithmique & programmation -> Algorithmes de tri Toutes les heures sont au format GMT + 1 Heure
 
Page 1 sur 1

 
Sauter vers:  
Index | créer forum gratuit | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation