import java.util.Date;public class Tri { /** * Recherche du pivot */ private static int partition(int t[], int deb, int fin){ int j = deb; int pivot = t[deb]; for (int i = deb + 1; i <= fin; i++) { if (t[i] < pivot) { //le pivot est plus grand que i donc on échange les valeur i et j j++; echanger(t, j, i); } } echanger(t, deb, j); return (j); } private static void tri_rapide(int tableau[], int deb, int fin){ if (deb < fin) { int positionPivot = partition(tableau, deb, fin); tri_rapide(tableau, deb, positionPivot - 1); tri_rapide(tableau, positionPivot + 1, fin); } } private static void echanger(int[] t, int i, int j) { int temp = t[i]; t[i] = t[j]; t[j] = temp; } public static void main(String[] arg) { int n = 1000000; int[] tab = new int[n]; int[] tab2 = new int[n]; int r = 0; // met dans le tableau les valeur au pire des cas n - i sinon random for (int i = n - 1; i > -1; i--){ r = (int)(Math.random()*n); tab[i] = r; tab2[i] = r; } //TRI RAPIDE //début du timer Date DDeb = new Date(); long DateDeb = DDeb.getTime(); // tri rapide System.out.println("Tri rapide:"); Tri.tri_rapide(tab, 0, tab.length - 1); // fin du timer Date DFin = new Date(); long dateFin = DFin.getTime(); System.out.println(dateFin - DateDeb + "ms"); }}