Advertisement
Guest User

Untitled

a guest
Jan 12th, 2017
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.23 KB | None | 0 0
  1. package structures_donnees.tri;
  2.  
  3. import java.util.*;
  4.  
  5. public class AlgosTri {
  6.  
  7. static int [] tableau;
  8. static int [] copieTab;
  9. static int n=1000000;
  10. static boolean AFFICHAGE=false;
  11.  
  12. public static void main(String[] args) {
  13.  
  14. long start,stop; //sert pour calculer le temps des tris
  15.  
  16. tableau=new int[n];
  17.  
  18. Random r=new Random();
  19. for(int i=0;i<=n-1;i++)
  20. tableau[i]=r.nextInt(1000); //on remplit le tableau aléatoirement
  21.  
  22. copieTab=(int[]) tableau.clone(); // on garde une copie pour pouvoir appliquer différentes méthodes de tri sur le même jeu de données
  23.  
  24. if(AFFICHAGE) afficherTableau();
  25. System.out.println();
  26.  
  27. start = System.nanoTime();
  28. //triSelection();
  29. stop = System.nanoTime();
  30.  
  31. if(AFFICHAGE) afficherTableau();
  32.  
  33.  
  34. System.out.println("temps de tri par sélection : " + (float) (stop - start)/1000000 +" ms\n");
  35.  
  36. tableau=(int[]) copieTab.clone(); // on remet le tableau dans l'état initial
  37.  
  38. start = System.nanoTime();
  39. triFusion(tableau,0,n-1);
  40. stop = System.nanoTime();
  41.  
  42. if(AFFICHAGE) afficherTableau();
  43.  
  44. System.out.println("temps de tri fusion : " + (float) (stop - start)/1000000 +" ms\n");
  45.  
  46.  
  47. tableau=(int[]) copieTab.clone(); // on remet le tableau dans l'état initial
  48.  
  49. start = System.nanoTime();
  50. Arrays.sort(tableau);
  51. stop = System.nanoTime();
  52.  
  53. if(AFFICHAGE) afficherTableau();
  54.  
  55. System.out.println("temps de tri java: " + (float) (stop-start)/1000000 +" ms\n");
  56.  
  57.  
  58. }
  59.  
  60. public static void afficherTableau(){
  61.  
  62. System.out.print("Tableau :");
  63.  
  64. for(int i=0;i<=n-1;i++)
  65. System.out.print(" "+tableau[i]);
  66.  
  67. System.out.println(".");
  68.  
  69. }
  70.  
  71. public static void triSelection(){
  72.  
  73. int min = 0;
  74. int tmp = 0;
  75.  
  76. for(int i = 0; i < n-1; ++i)
  77. {
  78. min = i;
  79. for(int j = i+1; j < n; ++j)
  80. {
  81. if(tableau[j] < tableau[min])
  82. min = j;
  83. }
  84. if(min != i)
  85. {
  86. tmp = tableau[i];
  87. tableau[i] = tableau[min];
  88. tableau[min] = tmp;
  89. }
  90. }
  91.  
  92. }
  93.  
  94. private static void triFusion(int tableau[],int deb,int fin)
  95. {
  96. if (deb!=fin)
  97. {
  98. int milieu=(fin+deb)/2;
  99. triFusion(tableau,deb,milieu);
  100. triFusion(tableau,milieu+1,fin);
  101. fusion(tableau,deb,milieu,fin);
  102. }
  103. }
  104.  
  105. private static void fusion(int tableau[],int deb1,int fin1,int fin2)
  106. {
  107. int deb2 = fin1+1;
  108.  
  109. int tab1[] = new int[fin1-deb1+1];
  110. for(int i = deb1;i<=fin1;i++) //On met la première partie du tableau dans un deuxième tableau
  111. {
  112. tab1[i-deb1]=tableau[i];
  113. }
  114.  
  115. int a = deb1; //premier compteur
  116. int b = deb2; //deuxième compteur
  117.  
  118. for(int i = deb1; i <= fin2;i++) //On parcours tout le tableau
  119. {
  120. if (a == deb2) //Tout a été trié, on break
  121. break;
  122. else if(b == (fin2+1))
  123. {
  124. tableau[i] = tab1[a-deb1];
  125. a++;
  126. }
  127. else if(tab1[a-deb1] < tableau[b])
  128. {
  129. tableau[i] = tab1[a-deb1];
  130. a++;
  131. }
  132. else
  133. {
  134. tableau[i] = tableau[b];
  135. b++;
  136. }
  137. }
  138. }
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement