/* * @program: Sort.java * @auteur: felipe@dift1010 * @date: 27/03/2004 * @revised: 10/04/2005 * @objet: un programme qui reuni l'ensemble des tris vus dans ce cours * @note: il existe des ameliorations des implementations fournies qui nuisent * a la lisibilite du code --> je ne donne que des versions simples et claires */ /** * La classe qui implemente les differents tris vus en cours */ class Sort { /** * @param t la reference sur le tableau * @param i indice dans t * @param j indice dans t * @return true * Permute dans t les valeurs d'indice i et j */ private static boolean swap(int [] t, int i, int j) { int temp = t[i]; t[i] = t[j]; t[j] = temp; return true; // inutile sauf pour le tri a bulle (oubliez) } /** * @param t la reference sur le tableau * Implementation possible du tri a bulle */ public static void bulle(int [] t) { boolean bulle=true; for (int passage=1; bulle; ++passage) { bulle = false; for (int i=0; it[i+1]) bulle = swap(t,i,i+1); } } /** * @param t la reference sur le tableau * Implementation possible du tri par selection */ public static void selection(int [] t) { int imin; for (int i=0; i=0) && (t[j] > memo) ; j--) t[j+1] = t[j]; t[j+1] = memo; } } /** * @param t la reference sur le tableau * @param d indice de debut de la plage du tableau a trier * @param f indice de fin de la plage du tableau a trier * Implementation possible du tri rapide */ public static void quick(int [] t, int d, int f) { if (d < f) { int pivot = selectPivot(t,d,f); int ipivot = partitionne(t,d,f,pivot); quick(t,d,ipivot-1); quick(t,ipivot+1,f); } } // same, mais le pivot est pris au milieu public static void quick2(int [] t, int d, int f) { if (d < f) { int pivot = selectPivot2(t,d,f); int ipivot = partitionne(t,d,f,pivot); quick2(t,d,ipivot-1); quick2(t,ipivot+1,f); } } /** * @param t la reference sur le tableau * @param d indice de debut de la plage du tableau a trier * @param f indice de fin de la plage du tableau a trier * Implementation possible du tri par fusion */ public static void fusion(int [] t, int d, int f) { if (df) || ((k < tmp.length) && (tmp[k] < t[j]))) t[i] = tmp[k++]; else t[i] = t[j++]; } /** * @param t la reference sur le tableau a trier * @param d indice de debut de la plage du tableau a trier * @param f indice de fin de la plage du tableau a trier * @return la valeur du pivot separateur * @note la premiere valeur est retournee comme pivot * ===> si vous voulez changer cela, faite un swap(t,d,p) ou p * est l'indice du pivot que vous avez selectionne */ private static int selectPivot(int [] t, int d, int f) {return t[d];} // simple eh ? // idem, mais le pivot est le milieu du tableau private static int selectPivot2(int [] t, int d, int f) { swap(t,d,(d+f)/2); return selectPivot(t,d,f); } /** * @param t la reference sur le tableau a trier * @param d indice de debut de la plage du tableau a trier (c'est egalement l'indice du pivot au depart) * @param f indice de fin de la plage du tableau a trier * @param pivot la valeur de partitionnement * @return la valeur du pivot separateur * @note met a gauche les valeurs inferieures au pivot, a droite les autres * est l'indice du pivot que vous avez selectionne */ private static int partitionne(int [] t, int d, int f, int pivot) { while (d < f) { while ((d = pivot)) --f; if (d = pivot } } } return d; // c'est l'indice du pivot } }