17 octobre 2013
4
17
/10
/octobre
/2013
04:30
Principe:
Le tri de Shell est une amélioration du tri par insertion en observant deux choses :
- Le Tri insertion est efficace si la liste est à peu près triée ;
- Le tri par insertion est inefficace en moyenne car il ne déplace les valeurs que d'une position par instruction (2).
Le tri de Shell trie chaque liste d'éléments séparés de n positions chacun avec le Tri insertion . L'algorithme effectue plusieurs fois cette opération en diminuant n jusqu'à n=1 ce qui équivaut à trier tous les éléments ensemble.
Pseudo code
procedure Tri_Shell (Tableau a [1: n] )
pour i variant de h en h faire
si a[hi+1] = a[3hi+1] alors
echanger a[i+1] et a[i]
permut = VRAI
fin si
fin pour
tant que permut = VRAI
fin procedure
Complexité: Θ(N2)
Le tri shell est une excellente optimisation du Tri insertion. Le nombre d'opération est de l'ordre n*n. En ce qui concerne la mémoire, très peu est nécessaire.
Implémentation en java
Class TriShell:
package pisix.ag51.trishell; import java.util.ArrayList; public class TriShell { int pas=0; int memoire,i,j; ArrayList<Integer> listeElementAtriee; TriShell(){ } public TriShell(ArrayList<Integer>listeElementAtriee){ this.listeElementAtriee = listeElementAtriee; } public ArrayList<Integer> tri(){ int longueur = listeElementAtriee.size(); while (pas<longueur){ pas = 3*pas+1; } while(pas!=0){ pas = pas/3; for(i=pas;i<longueur;i++){ memoire=listeElementAtriee.get(i); j=i; while((j>(pas-1)) && (listeElementAtriee.get(j-pas))>memoire){ //echange des valeurs listeElementAtriee.set(j, listeElementAtriee.get(j-pas)); j=j-pas; } listeElementAtriee.set(j, memoire); } } return listeElementAtriee; } public ArrayList<Integer> getListeElementAtriee() { return listeElementAtriee; } public void setListeElementAtriee(ArrayList<Integer> listeElementAtriee) { this.listeElementAtriee = listeElementAtriee; } }
Class Main:
package pisix.ag.trishell; import java.util.ArrayList; import pisix.ag.trishell.TriShell; public class RunTriShell { public static void main(String[] args) { // TODO Auto-generated method stub ArrayList<Integer> liste=new ArrayList<Integer>(); //Generation d'un tableau de maniere aléatoire de 150 000 éléments for(int i =0; i<150000;i++){ liste.add(i); liste.set(i, (int) (Math.random()*(149999-1)+1)); } //On passe la liste à trier à notre constructeur TriShell tri1 = new TriShell(liste); ArrayList<Integer> listeTriee; long deb = System.currentTimeMillis(); //Lancement du tri listeTriee = tri1.tri(); long fin = System.currentTimeMillis()-deb; System.out.println("Apres le tri shell les valeurs du Tableau sont :"); for(int list : listeTriee){ System.out.println(list); } //On affiche le temps d'éxécution de l'algo System.out.println("Temps d'execution en milliseconde : "+fin); } }
Courbe expérimentale:
Le graphique ci-dessous montre la progression du nombres d'instruction(temps (ms)) en fonction de la taille(Nombre d'éléments)
C'est tout pour le moment ....