Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package structures_donnees.tri;
- import java.util.*;
- public class AlgosTri {
- static int [] tableau;
- static int [] copieTab;
- static int n=1000000;
- static boolean AFFICHAGE=false;
- public static void main(String[] args) {
- long start,stop; //sert pour calculer le temps des tris
- tableau=new int[n];
- Random r=new Random();
- for(int i=0;i<=n-1;i++)
- tableau[i]=r.nextInt(1000); //on remplit le tableau aléatoirement
- 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
- if(AFFICHAGE) afficherTableau();
- System.out.println();
- start = System.nanoTime();
- //triSelection();
- stop = System.nanoTime();
- if(AFFICHAGE) afficherTableau();
- System.out.println("temps de tri par sélection : " + (float) (stop - start)/1000000 +" ms\n");
- tableau=(int[]) copieTab.clone(); // on remet le tableau dans l'état initial
- start = System.nanoTime();
- triFusion(tableau,0,n-1);
- stop = System.nanoTime();
- if(AFFICHAGE) afficherTableau();
- System.out.println("temps de tri fusion : " + (float) (stop - start)/1000000 +" ms\n");
- tableau=(int[]) copieTab.clone(); // on remet le tableau dans l'état initial
- start = System.nanoTime();
- Arrays.sort(tableau);
- stop = System.nanoTime();
- if(AFFICHAGE) afficherTableau();
- System.out.println("temps de tri java: " + (float) (stop-start)/1000000 +" ms\n");
- }
- public static void afficherTableau(){
- System.out.print("Tableau :");
- for(int i=0;i<=n-1;i++)
- System.out.print(" "+tableau[i]);
- System.out.println(".");
- }
- public static void triSelection(){
- int min = 0;
- int tmp = 0;
- for(int i = 0; i < n-1; ++i)
- {
- min = i;
- for(int j = i+1; j < n; ++j)
- {
- if(tableau[j] < tableau[min])
- min = j;
- }
- if(min != i)
- {
- tmp = tableau[i];
- tableau[i] = tableau[min];
- tableau[min] = tmp;
- }
- }
- }
- private static void triFusion(int tableau[],int deb,int fin)
- {
- if (deb!=fin)
- {
- int milieu=(fin+deb)/2;
- triFusion(tableau,deb,milieu);
- triFusion(tableau,milieu+1,fin);
- fusion(tableau,deb,milieu,fin);
- }
- }
- private static void fusion(int tableau[],int deb1,int fin1,int fin2)
- {
- int deb2 = fin1+1;
- int tab1[] = new int[fin1-deb1+1];
- for(int i = deb1;i<=fin1;i++) //On met la première partie du tableau dans un deuxième tableau
- {
- tab1[i-deb1]=tableau[i];
- }
- int a = deb1; //premier compteur
- int b = deb2; //deuxième compteur
- for(int i = deb1; i <= fin2;i++) //On parcours tout le tableau
- {
- if (a == deb2) //Tout a été trié, on break
- break;
- else if(b == (fin2+1))
- {
- tableau[i] = tab1[a-deb1];
- a++;
- }
- else if(tab1[a-deb1] < tableau[b])
- {
- tableau[i] = tab1[a-deb1];
- a++;
- }
- else
- {
- tableau[i] = tableau[b];
- b++;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement