1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
| public class Tris {
public static void triIndirect(int[] tab) {
rearrange(tab, calculTabIndex(tab));
}
//Stock les indice des cases du tableau dans un deuxièmme taleau
public static int[] calculTabIndex(int[] tab) {
int taille = tab.length;
int[] tix = new int[taille];
int pos = 0, n = 0;
for (int i = 0; i < taille; i++) {
for (int j = 0; j < taille; j++) {
if ((i != j) && (tab[i] > tab[j]))
pos++;
Compteur.IncrCpComparaison();
if ((i < j) && (tab[i] == tab[j]))
n++;
}
tix[i] = pos + n;
pos = 0;
n = 0;
}
return tix;
}
//Permet de creer le tableau trié
public static int[] rearrange(int[] tab, int[] tdx) {
int x = 0;
do {
if (x != tdx[x]) {
permute(tab, x, tdx[x]);
permute(tdx, x, tdx[x]);
} else
x++;
} while (x != tab.length);
return tab;
}
public static void permute(int[] tab, int i, int j) {
int temp = tab[i];
tab[i] = tab[j];
tab[j] = temp;
}
public static void triSelection(int[] tab) {
for (int i = 0; i < tab.length; i++) {
permute(tab, i, indiceDuMin(tab, i));
}
}
public static int indiceDuMin(int[] tab, int n) {
int min = tab[n], ind = n;
for (int i = n; i < tab.length; i++) {
if (tab[i] < min) {
Compteur.IncrCpComparaison();
min = tab[i];
ind = i;
}
}
return ind;
}
public static void triFusion(int tableau[]) {
int longueur = tableau.length;
if (longueur > 0) {
triFusion(tableau, 0, longueur - 1);
}
}
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;
// on recopie les ÈlÈments du dÈbut du tableau
int table1[] = new int[fin1 - deb1 + 1];
for (int i = deb1; i <= fin1; i++) {
table1[i - deb1] = tableau[i];
}
int compt1 = deb1;
int compt2 = deb2;
for (int i = deb1; i <= fin2; i++) {
if (compt1 == deb2) // c'est que tous les ÈlÈments du premier
// tableau ont ÈtÈ utilisÈs
{
break; // tous les ÈlÈments ont donc ÈtÈ classÈs
} else if (compt2 == (fin2 + 1)) // c'est que tous les ÈlÈments du
// second tableau ont ÈtÈ
// utilisÈs
{
tableau[i] = table1[compt1 - deb1]; // on ajoute les ÈlÈments
// restants du premier
// tableau
compt1++;
} else if (table1[compt1 - deb1] < tableau[compt2]) {
tableau[i] = table1[compt1 - deb1]; // on ajoute un ÈlÈment du
// premier tableau
compt1++;
} else {
tableau[i] = tableau[compt2]; // on ajoute un ÈlÈment du second
// tableau
compt2++;
}
}
}
public static void triRapide(int tableau[]) {
int longueur = tableau.length;
triRapide(tableau, 0, longueur - 1);
}
private static int partition(int tableau[], int deb, int fin) {
int compt = deb;
int pivot = tableau[deb];
for (int i = deb + 1; i <= fin; i++) {
if (tableau[i] < pivot) {
Compteur.IncrCpComparaison();
compt++;
permute(tableau, compt, i);
}
}
permute(tableau, deb, compt);
return (compt);
}
private static void triRapide(int tableau[], int deb, int fin) {
if (deb < fin) {
int positionPivot = partition(tableau, deb, fin);
triRapide(tableau, deb, positionPivot - 1);
triRapide(tableau, positionPivot + 1, fin);
}
}
} |
Partager