tri.java

 
 1 package tableaux;
 2 class tri { 
 3 // méthode utilisée pour les tris
 4 public static void echange(int[]t,int i,int j){
 5 int tmp=t[i];
 6 t[i]=t[j];
 7 t[j]=tmp;
 8 }
 9 public static void triselection(int[] t){
10 triselection(t,0,t.length-1);
11 }
12 public static void triinsertion(int[] t){
13 triinsertion(t,0,t.length-1);
14  }
15 public static void triinsertionbis(int[] t){
16 triinsertionbis(t,0,t.length-1);
17 }
18 public static void tribulle(int[]t){
19 tribulle(t,0,t.length-1);
20 }
21 // tri par sélection
22 // invariant de la boucle
23 // t est trié sur [l,i[
24 // pour tout j de [i,r] et tout k de [l,r[ t[j]>=t[k]
25 public static void triselection(int[] t, int l,int r){
26 for(int i=l;i<=r;i++){
27 int min=i;
28 for(int j=i+1;j<=r;j++)
29 if(t[j]<t[min])min=j;
30 echange(t,i,min);
31 }
32 }
33 // tri par insertion
34 // invariant de la boucle
35 // t est trié sur [l,i[
36 // l'élement t[i] est inséré à sa bonne position dans le t[l,i[
37 public static void triinsertion(int t[],int l,int r){
38 int i;
39 for(i=l;i<=r;i++)
40 for(int j=i;j>l;j--)
41 if(t[j]<t[j-1])echange(t,j-1,j);
42 }
43 // version améliorée: une sentinelle évite le test de débordement
44 // les échanges s'arrêtent dès que l'élément à insérer est à sa place
45 // simplification des échanges
46 public static void triinsertionbis(int []t,int l, int r){
47 int i;
48 for(i=r;i>l;i--)if(t[i]<t[i-1])echange(t,i-1,i);
49 for(i=l+2;i <=r;i++){
50 int j=i; int tmp=t[i];
51 while(tmp<t[j-1]){
52 t[j]=t[j-1];j--;
53 }
54 t[j]=tmp;
55 }
56 }
57 // tri-bulle
58 // invariant de la boucle (comme sélection)
59 // t est trié sur [l,i[
60 // pour tout j de [i,r] et tout k de [l,r[ t[j]>=t[k]
61 public static void tribulle(int[]t, int l,int r){
62  for(int i=l;i<=r;i++)
63 for(int j=r;j>i;j--)
64 if(t[j]<t[j-1])echange(t,j-1,j);
65 }
66 
67 }