I.T.A.G (DTS1)

Ce forum incha allah aura pour but d aider les etudiant de la DTS1 a en plus savoir cotee cours et tt que sa soit reseau ou devlopment
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Le tri Shell

Aller en bas 
AuteurMessage
mohcin



Messages : 26
Date d'inscription : 13/02/2008

MessageSujet: Le tri Shell   Mer 13 Fév - 9:53

Donald L. Shell proposa, en 1959, une variante du tri par insertion. Ce tri consiste à trier séparément des sous-suites de la table, formées par les éléments répartis de h en h. Empiriquement, Shell propose la suite d'incréments vérifiant h1 = 1, hn+1 = 3hn+1 en réalisant les tris du plus grand incrément possible vers le plus petit.

Dans la démo ci-dessous - en raison de la faible taille de la table à trier - on a choisi h1=1, h2=2, h3=4, h4=5, h5=10.


Votre navigateur ne peut pas lancer cette applet !


--------------------------------------------------------------------------------

Voici, en Caml, l'algorithme du tri Shell :


let tri vecteur h = let i = ref 0 and j = ref 0 in
for k=0 to (h-1) do
begin
i:=k+h;
while (!i < vect_length(vecteur)) do
let x = vecteur.(!i) in
begin
j:=!i - h;
while (!j>=0) && vecteur.(!j)>x do
vecteur.(!j+h) <- vecteur.(!j);
j:=!j - h;
vecteur.(!j + h) <- x;
done;
i:=!i + h;
end
done;
end
done;;
let tri_shell vecteur = let h = ref 1 and l = vect_length(vecteur)+1 in
begin
while !h<(l/9) do h:=3 * !h + 1;done;
while (!h>0) do
begin
tri vecteur !h;
h:=!h / 3;
end
done;
end;;
tri : 'a vect -> int -> unit = fun
tri_shell : 'a vect -> unit = fun



--------------------------------------------------------------------------------

La complexité du tri par Shell est en O(n2) dans le pire des cas.

Le graphique ci-contre montre la progression du nombre d'instruction en fonction de la taille des données.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
 
Le tri Shell
Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Anti-Shell!!
» VOILA LE RéSULTAT
» La grotte aux coquillages "Shell grotto" : Angleterre

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
I.T.A.G (DTS1) :: Cours de Réseaux et Development :: Devlopment :: cours-
Sauter vers: