tableaux : Arrays

Cette  classe contient des méthodes statiques permettant de manipuler de tableaux  :

• Recherche, recherche dichotomique
• Tris
• Remplissage
• Egalité
• toString()

La méthode static String toString(X[] a) retourne une chaîne de caractères contenant les éléments du tableau (convertis en chaîne de caractères), séparés par des virgules, et entre crochets.

La méthode static boolean equals(X[] a, X[] a2)  où X peut être un type primitif ou un Object retourne true si les deux tableaux sont égaux et false sinon. Deux tableaux sont égaux s’ils contiennent le même nombre d’éléments, et si les éléments de même rang sont égaux. Si des éléments du tableau peuvent être des tableaux, il faut utiliser la méthode deepEquals(X[] a, X[] a2).

La méthode static void fill(X[] a, X val) affecte la valeur val à tous les éléments du tableau a.

La méthode static int binarySearch(X[] a, X cle) effectue une recherche  de cle dans le tableau trié a. La méthode retourne l’indice de l’élément s’il existe, et – pointDInsertion-1 si cle ne se trouve pas dans le tableau. La valeur pointDInsertion est le rang où la clé serait ajoutée, si on l’ajoutait au tableau. C'est le rang du premier élément plus grand que l'élément cherché, ou la taille du tableau.

public static int binarySearch(int[] a, int cle) {
   int debut = 0;
   int fin = a.length-1;
   while (debut <= fin) {
      int milieu =( debut + fin)/2;
      if (a[milieu]< cle)   debut = milieu + 1;
      else if (a[milieu]> cle) fin = milieu - 1;
           else return milieu; // trouvé
   }
   return -(debut + 1); // pas trouvé.
}

La méthode static void sort(Object[] a) est programmée en utilisant :

• Un tri rapide si X est un type primitif. adapté de Jon  L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (Novembre 1993). Cet algorithme n’est pas stable.
• Un tri par fusion si X est un Object. Cet algorithme est stable.

1 Tri  rapide

public static void sort(int[] a) {
   sort(a, 0, a.length);
}

private static void sort(int [] x, int off,  int len) {
   // Tri par insertion si len <7
   if (len < 7) {
      for (int i=off; i<len+off; i++)
         for (int j=i; j>off && x[j-1]>x[j]; j--)
            echanger(x, j, j-1);
      return;
   }
   // Choix du pivot 
   int m = off + len/2;  // pour les petits tableaux, 

   // c’est l’élément du milieu
   if (len > 7) {
      int l = off;
      int n = off + len - 1;
      if (len > 40) { // Pour les grands tableaux le médian de 9
         int s = len/8;
         l = med3(x, l,  l+s, l+2*s);
         m = med3(x, m-s,   m,   m+s);
         n = med3(x, n-2*s, n-s, n);
      }
      m = med3(x, l, m, n); // tableaux moyen médian de 3
   }
   int pivot = x[m];
   
   // établir l’invariant: v* (<v)* (>v)* v*
   int a = off, b = a, c = off + len - 1, d = c;
   while(true) {
      while (b <= c && x[b] <= pivot) {
         if (x[b] == pivot) echanger(x, a++, b);
         b++;
      }
      while (c >= b && x[c] >= pivot) {
         if (x[c] == pivot) echanger(x, c, d--);
         c--;
      }
      if (b > c)  break;
      echanger(x, b++, c--);
   }
   
   // mettre les valeurs égales au pivot au milieu
   int s, n = off + len;
   s = Math.min(a-off, b-a  );  echanger(x, off, b-s, s);
   s = Math.min(d-c,   n-d-1);  echanger(x, b,   n-s, s);
   
   // Appels récursifs sur les éléments non pivot.
   if ((s = b-a) > 1) sort(x, off, s);
   if ((s = d-c) > 1) sort(x, n-s, s);
}

private static void echanger(int [] x, int a, int b) {
   int t = x[a];
   x[a] = x[b];
   x[b] = t;
}

private static void echanger(int x[], int a, int b, int n) {
   for (int i=0; i<n; i++, a++, b++)
      echanger(x, a, b);
}

private static int med3(int x[], int a, int b, int c) {
   return (x[a] < x[b] 
                ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) 
                : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}

2 Tri  par fusion

public static void sort(Object[] a) {
   Object [] aux =(Object[])a.clone();
   mergeSort(aux, a, 0, a.length);
}

private static void mergeSort(Object src[], Object dest[], int deb, int fin) {<
   int longueur = fin - deb;
   // tri par insertion pour les petits tableaux
   if (longueur < 7) {
      for (int i=deb; i<fin; i++)
         for (int j=i; j>deb && ((Comparable)dest[j-1]).compareTo ((Comparable)dest[j]) >0; j--)
            swap(dest, j, j-1);
      return;
   }
   // trier les 2 moitiés de dest vers src
   int milieu = (deb + fin)/2;
   mergeSort(dest, src, deb, milieu);
   mergeSort(dest, src, milieu, fin);
   // Si src est ordonné, copier src dans dest
   if (((Comparable)src[milieu-1]).compareTo((Comparable) src[milieu]) <= 0) {
      System.arraycopy(src, deb, dest, fin, longueur);
      return;
   }
   /// fusionner les 2 moitiés de src vers dest
   for(int i = deb, p = deb, q = milieu; i < fin; i++) {
      if (q>=fin || p<milieu && ((Comparable)src[p]).compareTo(src[q])<=0)
           dest[i] = src[p++];
      else est[i] = src[q++];
   }
}

haut de la page