SHARE
TWEET

Untitled

a guest Jan 12th, 2017 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
Top