Séance 6 — Ensembles disjoints et tris

Union-find, tri par insertion, tri fusion, tri rapide et borne inférieure

Séance 6 de Structures de données et algorithmes avancés : union-find, tri par insertion, tri fusion, tri rapide et borne inférieure.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

NoteNavigation conceptuelle

Amont. Les tableaux et l’analyse des coûts (Séances 1 et 2) ; les arbres, le tas binaire et le tri par tas (Séance 4) ; l’algorithme de Kruskal, dont le test de cycle parcourait la forêt à chaque arête (Séance 5).

Aval. Cette séance clôt le cours : sa dernière partie rassemble les structures des six séances, leurs opérations et leurs coûts.

ImportantObjectifs
  • Dérouler QuickFind et QuickUnion sur une suite d’unions, avec les tableaux id[] et parent[] et la forêt qu’ils représentent.
  • Construire l’union pondérée par la taille, démontrer que la hauteur de la forêt reste au plus \(\log_2 n\), et appliquer la compression de chemin.
  • Refaire l’algorithme de Kruskal de la Séance 5 avec union-find et mesurer le gain.
  • Dérouler le tri par insertion, le tri fusion et la partition du tri rapide, et compter leurs comparaisons.
  • Reconnaître un tri stable et expliquer le pire cas du tri rapide.
  • Démontrer la borne \(\Omega(n\log n)\) des tris par comparaison à l’aide d’un arbre de décision.

Tous les programmes de ce document sont en Java 17 ; ils ont été compilés par javac --release 17 -Xlint:all et exécutés avec OpenJDK 21 sur Linux x86_64, et chaque sortie reproduite est celle de cette exécution. Les classes du cours sont QuickFindUF, QuickUnionUF, WeightedQuickUnionUF et PathCompressionUF, qui réalisent l’interface UF, la classe KruskalUF, puis TriInsertion, TriFusion, TriRapide et TriTas, qui héritent de Tri. Leurs compteurs publics (acces(), comparaisons, acces) servent à observer le coût des algorithmes. Le tas est la classe BinaryMinHeap de la Séance 4, et le graphe pondéré la classe GraphePondere de la Séance 5.

Le problème des ensembles disjoints

En Séance 5, l’algorithme de Kruskal examinait les arêtes par poids croissant et rejetait celles dont les deux extrémités étaient déjà reliées dans la forêt construite. Pour le savoir, il lançait un parcours en largeur de la forêt à chaque arête : jusqu’à \(V\) sommets atteints par arête, \(38\,476\,757\) sommets atteints au total pour un graphe de \(V=4\,000\) sommets et \(16\,000\) arêtes. La question posée à chaque arête est pourtant toujours la même : « ces deux sommets sont-ils dans le même morceau ? », et la forêt n’évolue que d’une façon : deux morceaux se réunissent. La structure de cette séance répond à cette question sans parcours.

Le même besoin apparaît dans un réseau électrique rural. Huit villages de la Petite Côte sont raccordés au réseau, liaison après liaison, dans l’ordre des travaux (à gauche) ; à droite figurent les liaisons possibles et leur coût en millions de FCFA, qui serviront à l’algorithme de Kruskal en section 6. Deux villages sont sur le même réseau s’ils sont reliés par une suite de liaisons.

NoteEnsembles disjoints (union-find)

Une structure d’ensembles disjoints maintient une partition des éléments \(0,\dots,n-1\) en composantes. Au départ, chaque élément forme sa propre composante. L’opération union(p, q) réunit la composante de \(p\) et celle de \(q\) ; find(p) rend un identifiant de la composante de \(p\), le même pour tous les éléments d’une composante ; connected(p, q) teste si \(\texttt{find(p)}=\texttt{find(q)}\) ; count() rend le nombre de composantes.

L’interface Java du cours suit Sedgewick et Wayne (§ 1.5). La méthode connected est une méthode par défaut : elle s’écrit une fois pour toutes à partir de find.

int find(int p);                // identifiant de la composante de p
void union(int p, int q);       // reunir les composantes de p et de q
int count();                    // nombre de composantes

default boolean connected(int p, int q) {
    return find(p) == find(q);  // meme composante
}

Les quatre réalisations de la séance diffèrent par la manière de ranger les composantes dans un tableau. Leur coût se mesure par le compteur acces(), qui additionne les lectures et les écritures du tableau id[] ou parent[] : c’est la ressource que les algorithmes consomment, indépendamment de la machine.

QuickFind

La réalisation la plus directe range, pour chaque élément \(p\), l’identifiant de sa composante dans id[p]. Au départ, id[p] vaut \(p\). Deux éléments sont dans la même composante si et seulement si leurs cases contiennent la même valeur ; find ne coûte donc qu’un accès. En contrepartie, union(p, q) doit donner à toute la composante de \(p\) l’identifiant de celle de \(q\), et pour trouver ces éléments elle lit toutes les cases du tableau.

private final int[] id;  // id[p] : composante de p
private int count;       // nombre de composantes
private long acces;      // acces a id[]

public QuickFindUF(int n) {
    id = new int[n];
    for (int i = 0; i < n; i++) id[i] = i;
    count = n;
}

public int find(int p) {
    acces++;
    return id[p];
}
public void union(int p, int q) {
    int pid = find(p);
    int qid = find(q);
    if (pid == qid) return;  // deja reunis
    for (int i = 0; i < id.length; i++) {
        acces++;
        if (id[i] == pid) {
            id[i] = qid;
            acces++;
        }
    }
    count--;
}

Les variables pid et qid sont lues avant la boucle : la case id[p] elle-même change pendant la boucle, et la comparaison id[i] == pid doit porter sur l’ancienne valeur. Une valeur \(v\) présente dans le tableau vérifie toujours \(\texttt{id[}v\texttt{]}=v\) : l’élément \(v\) appartient à la composante qu’il identifie. Le tableau représente ainsi une forêt où chaque élément pointe directement sur l’identifiant de sa composante, comme le montrent les figures ci-dessous.

Exemple pas à pas : les raccordements des huit villages

Le programme suivant applique les sept raccordements (0–1, 1–2, 2–3, 4–5, 6–7, 5–7, 3–7) avec une version de union réduite à l’essentiel, sans compteur. Le tableau RACC contient ces paires.

static int[] id = {0, 1, 2, 3, 4, 5, 6, 7};
static void union(int p, int q) {
    int pid = id[p];
    int qid = id[q];
    if (pid == qid) return;
    for (int i = 0; i < id.length; i++) {
        if (id[i] == pid) id[i] = qid;
    }
}
// dans main :
for (int[] r : RACC) union(r[0], r[1]);
System.out.println(id[0] == id[6]);
System.out.println(Arrays.toString(id));
Étape Lignes Instruction Effet Écrit
1 1 id = {0, 1, ..., 7} Huit villages, chacun seul dans sa composante : id[p] vaut \(p\).
2 3–7, 11 union(0, 1) union(0, 1) : pid \(=0\), qid \(=1\) ; la boucle lit les 8 cases et la case 0 passe à 1.
3 3–7, 11 union(1, 2) union(1, 2) : pid \(=1\), qid \(=2\) ; la boucle lit les 8 cases et les cases 0, 1 passent à 2.
4 3–7, 11 union(2, 3) union(2, 3) : pid \(=2\), qid \(=3\) ; la boucle lit les 8 cases et les cases 0, 1, 2 passent à 3.
5 3–7, 11 union(4, 5) union(4, 5) : pid \(=4\), qid \(=5\) ; la boucle lit les 8 cases et la case 4 passe à 5.
6 3–7, 11 union(6, 7) union(6, 7) : pid \(=6\), qid \(=7\) ; la boucle lit les 8 cases et la case 6 passe à 7.
7 3–7, 11 union(5, 7) union(5, 7) : pid \(=5\), qid \(=7\) ; la boucle lit les 8 cases et les cases 4, 5 passent à 7.
8 3–7, 11 union(3, 7) union(3, 7) : pid \(=3\), qid \(=7\) ; les quatre cases de valeur 3 passent à 7.
9 12 println(id[0] == id[6]) connected(0, 6) se lit en deux accès : id[0] et id[6] valent 7. true
10 13 println(Arrays.toString(id)) 7 unions, chacune a lu les 8 cases : une union coûte \(\Theta(n)\), un find un accès. [7, 7, 7, 7, 7, 7, 7, 7]

Chaque union lit les huit cases, quel que soit le nombre de cases modifiées. Les états ci-dessous sont ceux des étapes 4 et 8 : à l’étape 4, union(2, 3) fait passer les trois cases de valeur 2 à la valeur 3 ; à l’étape 8, union(3, 7) réunit les deux dernières composantes, et les quatre cases de valeur 3 prennent la valeur 7. Les cases modifiées sont encadrées en rouge.


Étape 4 : union(2, 3)


Étape 8 : union(3, 7)

Sortie \(\rightarrow\)

true
[7, 7, 7, 7, 7, 7, 7, 7]

Une union qui réunit deux composantes coûte au moins \(n+3\) accès (deux find, \(n\) lectures et au moins une écriture), quelle que soit la taille des composantes : \(n-1\) unions, le nombre nécessaire pour tout réunir, coûtent donc au moins \((n-1)(n+3)\) accès, de l’ordre de \(n^2\). Pour un million d’éléments, cela fait \(10^{12}\) accès : QuickFind ne convient qu’aux petites partitions.

QuickUnion

QuickUnion inverse le compromis. Le tableau parent[] décrit une forêt : parent[p] est le parent de \(p\), et une racine est son propre parent. L’identifiant d’une composante est la racine de son arbre. find(p) remonte de parent en parent jusqu’à la racine ; union(p, q) cherche les deux racines et place la première sous la seconde, en une seule écriture.

protected final int[] parent;
protected int count;
protected long acces;   // acces a parent[]

public QuickUnionUF(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    count = n;
}

public int find(int p) {
    acces++;            // premier test
    while (p != parent[p]) {
        p = parent[p];  // monter
        acces += 2;     // lecture + test
    }
    return p;           // la racine
}
public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    parent[i] = j;  // i sous j
    acces++;
    count--;
}

Pour un élément de profondeur \(d\) (le nombre de liens qui le séparent de sa racine), la boucle de find teste \(d+1\) fois la condition et monte \(d\) fois : \(2d+1\) accès. Le coût de find, et donc celui de union, dépend de la hauteur de la forêt, la plus grande profondeur d’un élément.

Exemple pas à pas : les mêmes raccordements

static int[] parent = {0, 1, 2, 3, 4, 5, 6, 7};
static int find(int p) {
    while (p != parent[p]) p = parent[p];
    return p;
}
static void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    parent[i] = j;
}
// dans main :
for (int[] r : RACC) union(r[0], r[1]);
System.out.println(find(0) == find(6));
Étape Lignes Instruction Effet Écrit
1 1 parent = {0, 1, ..., 7} Huit arbres d’un seul nœud : chaque élément est sa propre racine.
2 3–4, 7–10, 13 union(0, 1) union(0, 1) : 0 et 1 sont des racines ; parent[0] \(=1\).
3 3–4, 7–10, 13 union(1, 2) union(1, 2) : 1 et 2 sont des racines ; parent[1] \(=2\).
4 3–4, 7–10, 13 union(2, 3) union(2, 3) : 2 et 3 sont des racines ; parent[2] \(=3\).
5 3–4, 7–10, 13 union(4, 5) union(4, 5) : 4 et 5 sont des racines ; parent[4] \(=5\).
6 3–4, 7–10, 13 union(6, 7) union(6, 7) : 6 et 7 sont des racines ; parent[6] \(=7\).
7 3–4, 7–10, 13 union(5, 7) union(5, 7) : 5 et 7 sont des racines ; parent[5] \(=7\).
8 3–4, 7–10, 13 union(3, 7) union(3, 7) : 3 et 7 sont des racines ; parent[3] \(=7\).
9 3–4, 14 println(find(0) == find(6)) find(0) monte 0 → 1 → 2 → 3 → 7 : 4 liens, 9 accès ; find(6) : 6 → 7. La hauteur est 4. true

Les trois premiers raccordements construisent une chaîne : union(0, 1) place 0 sous 1, union(1, 2) place 1 sous 2, puis union(2, 3) place 2 sous 3. La racine du premier argument passe toujours sous celle du second, sans regarder la taille des arbres. À l’étape 8, union(3, 7) place la racine 3 sous la racine 7, et l’élément 0 se retrouve à 4 liens de la racine : find(0) suit 0, 1, 2, 3, 7, soit 9 accès.


Étape 4 : une chaîne de hauteur 3


Étape 8 : union(3, 7), hauteur 4

Sortie \(\rightarrow\)

true

Le pire cas de QuickUnion

Rien n’empêche la chaîne de s’allonger d’un lien à chaque union. Le programme suivant appelle union(0, i) pour \(i=1,\dots,n-1\) : avant l’appel \(i\), l’élément 0 est au bas d’une chaîne de \(i-1\) liens, find(0) la remonte en entier, et la racine \(i-1\) passe sous \(i\). Les mêmes appels sont faits sur l’union pondérée de la section suivante.

for (int n : new int[] {1000, 2000, 4000, 8000}) {
    QuickUnionUF qu = new QuickUnionUF(n);
    WeightedQuickUnionUF wqu = new WeightedQuickUnionUF(n);
    for (int i = 1; i < n; i++) {
        qu.union(0, i);   // la racine de 0 sous i
        wqu.union(0, i);
    }
    System.out.printf(Locale.ROOT, "%4d : QuickUnion %8d acces, hauteur %4d ; "
        + "ponderee %5d acces, hauteur %d%n", n, qu.acces(), qu.hauteur(),
        wqu.acces(), wqu.hauteur());
}

Sortie \(\rightarrow\)

1000 : QuickUnion   999999 acces, hauteur  999 ; ponderee  2997 acces, hauteur 1
2000 : QuickUnion  3999999 acces, hauteur 1999 ; ponderee  5997 acces, hauteur 1
4000 : QuickUnion 15999999 acces, hauteur 3999 ; ponderee 11997 acces, hauteur 1
8000 : QuickUnion 63999999 acces, hauteur 7999 ; ponderee 23997 acces, hauteur 1

L’appel \(i\) coûte \(2(i-1)+1\) accès pour find(0), 1 pour find(i) et 1 pour l’écriture : au total \(\sum_{i=1}^{n-1}(2i+1)=n^2-1\) accès, et une hauteur finale de \(n-1\). Une suite d’unions bien choisie rend QuickUnion aussi coûteux que QuickFind, et la forêt dégénère en liste, comme un arbre binaire de recherche rempli dans l’ordre (Séance 4).

L’union pondérée

La dégénérescence vient de ce que union place parfois le grand arbre sous le petit. L’union pondérée par la taille range, à la racine \(r\) de chaque arbre, le nombre d’éléments de l’arbre, taille[r] ; elle place toujours la racine du plus petit arbre sous celle du plus grand, et à égalité la racine de \(q\) sous celle de \(p\), comme Sedgewick et Wayne. Seule la méthode union change ; find est celui de QuickUnion. Les lectures et écritures de taille[], en nombre constant par union, ne sont pas comptées dans acces().

protected final int[] taille;  // taille[r], r racine

@Override
public void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    if (taille[i] < taille[j]) {  // i sous j
        parent[i] = j;
        taille[j] += taille[i];
    } else {                      // j sous i
        parent[j] = i;
        taille[i] += taille[j];
    }
    acces++;
    count--;
}
NoteHauteur de l’union pondérée

Avec l’union pondérée par la taille, la profondeur de tout élément d’une forêt de \(n\) éléments est au plus \(\log_2 n\).

La démonstration suit un élément \(x\). Sa profondeur n’augmente que lorsque la racine de son arbre \(T_1\) passe sous la racine d’un autre arbre \(T_2\), et elle augmente alors de 1. La règle de l’union garantit \(|T_2|\geq|T_1|\) : l’arbre qui contient \(x\) après l’union a au moins \(2|T_1|\) éléments. La taille de l’arbre de \(x\) au moins double donc à chaque augmentation de sa profondeur ; partie de 1, elle ne peut pas dépasser \(n\), ce qui permet au plus \(\log_2 n\) doublements. Une union ou un find coûte donc \(\mathcal{O}(\log n)\) accès. Le pire cas de la section précédente le confirme : avec l’union pondérée, union(0, i) place chaque nouvel élément sous la racine 0, la forêt garde une hauteur de 1, et les \(n-1\) unions coûtent \(3(n-1)\) accès.

L’union par le rang (CLRS, § 19.3) range à la racine un majorant de la hauteur au lieu de la taille, et place la racine de rang plus petit sous l’autre ; elle donne la même borne de hauteur, par un argument analogue.

Exemple pas à pas : les mêmes raccordements

static void union(int p, int q) {
    int i = find(p);
    int j = find(q);
    if (i == j) return;
    if (taille[i] < taille[j]) {
        parent[i] = j;
        taille[j] += taille[i];
    } else {
        parent[j] = i;
        taille[i] += taille[j];
    }
}
// dans main :
for (int[] r : RACC) union(r[0], r[1]);
System.out.println(find(7) + " " + taille[find(7)]);
Étape Lignes Instruction Effet Écrit
1 2–5, 9–10, 14 union(0, 1) Mêmes raccordements, find de QuickUnion ; au départ, taille[i] \(=1\) : 1 passe sous 0, taille[0] \(=2\).
2 2–5, 9–10, 14 union(1, 2) union(1, 2) : racines 0 et 2 ; taille[0] \(=2\geq1\) : 2 passe sous 0, taille[0] \(=3\).
3 2–5, 9–10, 14 union(2, 3) union(2, 3) : racines 0 et 3 ; taille[0] \(=3\geq1\) : 3 passe sous 0, taille[0] \(=4\).
4 2–5, 9–10, 14 union(4, 5) union(4, 5) : racines 4 et 5 ; tailles égales (1) : 5 passe sous 4, taille[4] \(=2\).
5 2–5, 9–10, 14 union(6, 7) union(6, 7) : racines 6 et 7 ; tailles égales (1) : 7 passe sous 6, taille[6] \(=2\).
6 2–5, 9–10, 14 union(5, 7) union(5, 7) : racines 4 et 6 ; tailles égales (2) : 6 passe sous 4, taille[4] \(=4\).
7 2–5, 9–10, 14 union(3, 7) union(3, 7) : racines 0 et 4 ; tailles égales (4) : 4 passe sous 0, taille[0] \(=8\).
8 15 println(find(7) + ...) find(7) : 7 → 6 → 4 → 0 ; hauteur 3 \(=\log_2 8\), contre 4 pour QuickUnion. 0 8

Les trois premières unions, qui construisaient une chaîne avec QuickUnion, construisent ici une étoile : 1, 2 et 3 passent l’un après l’autre sous la racine 0, dont l’arbre est le plus grand. À l’étape 6, union(5, 7) réunit deux arbres de 2 éléments : à égalité, la racine 6 (celle de \(q\)) passe sous la racine 4. À l’étape 7, union(3, 7) réunit deux arbres de 4 éléments, et la racine 4 passe sous 0 : la hauteur atteint 3, exactement \(\log_2 8\), avec 7 au bas du chemin 7, 6, 4, 0.


Étape 3 : une étoile de racine 0


Étape 7 : deux arbres de 4 réunis

Sortie \(\rightarrow\)

0 8

La compression de chemin

Un find parcourt un chemin jusqu’à la racine ; une fois la racine connue, rien n’empêche de rattacher directement à elle chaque élément rencontré. C’est la compression de chemin : le find suivant de ces éléments, et de tous leurs descendants, sera plus court. La classe PathCompressionUF hérite de l’union pondérée et ne remplace que find, qui fait deux passages.

@Override
public int find(int p) {
    int racine = p;
    acces++;
    while (racine != parent[racine]) {
        racine = parent[racine];
        acces += 2;
    }
    while (p != racine) {    // second passage
        int suivant = parent[p];
        parent[p] = racine;  // rattache a la racine
        p = suivant;
        acces += 2;
    }
    return racine;
}

Le second passage lit puis réécrit parent[p] pour chaque élément du chemin : un find de profondeur \(d\) coûte \(4d+1\) accès, contre \(2d+1\) sans compression, mais les profondeurs diminuent pour la suite.

Exemple pas à pas : la forêt de QuickUnion

La compression s’applique à toute forêt. Pour montrer un long chemin, le programme part de la forêt finale de QuickUnion (section 3), où l’élément 0 est à 4 liens de la racine : parent \(=\) [1, 2, 3, 7, 5, 7, 7, 7].

static int find(int p) {
    int racine = p;
    while (racine != parent[racine]) {
        racine = parent[racine];
    }
    while (p != racine) {
        int suivant = parent[p];
        parent[p] = racine;
        p = suivant;
    }
    return racine;
}
// dans main :
System.out.println(find(0));
System.out.println(Arrays.toString(parent));
Étape Lignes Instruction Effet Écrit
1 2, 14 find(0) ; racine = p find(0) sur la forêt finale de QuickUnion ; racine part de 0.
2 3–4 racine = parent[racine] racine \(=1\) : la première boucle monte d’un niveau.
3 3–4 racine = parent[racine] racine \(=2\) : la première boucle monte d’un niveau.
4 3–4 racine = parent[racine] racine \(=3\) : la première boucle monte d’un niveau.
5 3–4 racine = parent[racine] racine \(=7\) : c’est la racine, la boucle s’arrête.
6 6–9 p = 0 : parent[p] = racine \(p=0\) : parent[0] passe de 1 à 7, puis \(p=1\).
7 6–9 p = 1 : parent[p] = racine \(p=1\) : parent[1] passe de 2 à 7, puis \(p=2\).
8 6–9 p = 2 : parent[p] = racine \(p=2\) : parent[2] passe de 3 à 7, puis \(p=3\).
9 6–9 p = 3 : parent[p] = racine \(p=3\) : parent[3] vaut déjà 7, la case est réécrite ; \(p=7\).
10 6, 11, 14 return racine ; println \(p=7\), fin de la boucle ; find(0) rend 7, le chemin est aplati. 7
11 15 println(Arrays.toString(parent)) Hauteur 2 au lieu de 4 : un nouveau find(0) ne suit qu’un lien. [7, 7, 7, 7, 5, 7, 7, 7]

Le premier passage (étapes 2 à 5) suit 0, 1, 2, 3 jusqu’à la racine 7 sans rien modifier. Le second (étapes 6 à 9) reprend le chemin depuis 0 : chaque élément est rattaché à 7, et la variable suivant garde son ancien parent pour poursuivre. L’élément 3, déjà fils de 7, voit sa case réécrite à l’identique. La hauteur passe de 4 à 2 : le plus long chemin est désormais 4, 5, 7, que ce find n’a pas visité.


Étape 5 : la racine est trouvée


Étape 10 : le chemin est aplati

Sortie \(\rightarrow\)

7
[7, 7, 7, 7, 5, 7, 7, 7]

Les quatre versions mesurées

Le programme suivant tire des paires \((p, q)\) au hasard parmi \(n\) éléments, jusqu’à ce qu’une seule composante reste (Paires.jusquaConnexe), puis soumet les mêmes paires aux quatre classes : pour chaque paire, un connected, puis un union si la paire n’est pas encore reliée. Il écrit le nombre de paires et, pour chaque classe, le nombre moyen d’accès par paire.

Random r = new Random(2026);
System.out.println("    n  paires  QuickFind QuickUnion ponderee compression");
for (int n = 1000; n <= 64000; n *= 2) {
    int[][] paires = Paires.jusquaConnexe(n, r);
    UF[] ufs = {new QuickFindUF(n), new QuickUnionUF(n),
        new WeightedQuickUnionUF(n), new PathCompressionUF(n)};
    System.out.printf("%5d %7d", n, paires.length);
    for (UF uf : ufs) {
        for (int[] x : paires) {
            if (!uf.connected(x[0], x[1])) uf.union(x[0], x[1]);
        }
        double parPaire = (double) uf.acces() / paires.length;
        System.out.printf(Locale.ROOT, " %10.1f", parPaire);
    }
    System.out.println();
}

Sortie \(\rightarrow\)

    n  paires  QuickFind QuickUnion ponderee compression
 1000    3084      369.8      362.6       10.0       11.3
 2000    9800      462.5      787.0        9.9       10.9
 4000   21283      848.7     1610.8       10.0       10.8
 8000   36902     1956.8     3093.5       10.3       10.9
16000   75882     3802.7     6205.4       10.1       10.9
32000  223346     5158.4    13441.6       10.1       10.6
64000  327882    14031.2    24681.4       10.2       10.8

QuickFind et QuickUnion coûtent des milliers d’accès par paire, qui croissent avec \(n\) (\(\times38\) et \(\times68\) de \(1\,000\) à \(64\,000\)) : pour \(n=64\,000\), \(14\,031\) et \(24\,681\). Dès \(n=2\,000\), QuickUnion est même plus coûteux que QuickFind sur ces paires : ses arbres atteignent une hauteur de \(11\,236\) pour \(n=64\,000\) (374 pour \(n=2\,000\)). L’union pondérée reste à une dizaine d’accès par paire (10,2 pour \(n=64\,000\)), avec une hauteur de 7, bien sous \(\log_2 64\,000\approx16\). La compression ramène la hauteur à 1 ou 2, mais paie les écritures de son second passage : 10,8 accès par paire. Sur des arbres déjà bas, son intérêt n’est pas un gain mesurable ici, mais une garantie.

NoteCoût de l’union pondérée avec compression

Avec union pondérée (par la taille ou par le rang) et compression de chemin, une suite de \(m\) opérations sur \(n\) éléments coûte \(\mathcal{O}(m\,\alpha(n))\), où \(\alpha\) est une fonction inverse de la fonction d’Ackermann ; \(\alpha(n)\leq4\) pour toute valeur de \(n\) représentable en pratique (Tarjan, 1975 ; CLRS, § 19.4, pour l’union par le rang). Le coût amorti d’une opération est donc presque constant.

AvertissementCe que la structure ne fait pas

La structure ne sait que réunir : une liaison coupée ne se retire pas, et une composante ne se sépare pas. Les éléments sont les entiers \(0,\dots,n-1\) ; des noms de villages passent d’abord par une table de hachage (Séance 3) qui leur associe un numéro.

Kruskal avec union-find

L’algorithme de Kruskal de la Séance 5 devient plus court avec union-find : relies(foret, v, w) devient uf.connected(v, w), et l’ajout de l’arête à la forêt devient uf.union(v, w). La forêt n’est plus construite comme un graphe ; seule la partition des sommets compte.

private void construire(GraphePondere g) {
    BinaryMinHeap<Arete> tas = new BinaryMinHeap<>();
    for (Arete e : g.aretes()) tas.insert(e);
    while (!tas.isEmpty() && arbre.size() < g.V() - 1) {
        Arete e = tas.extractMin();
        examinees++;
        if (uf.connected(e.v, e.w)) {    // meme composante : cycle
            rejets++;
            continue;
        }
        uf.union(e.v, e.w);
        arbre.add(e);
        poids += e.poids;
    }
    comparaisonsTas = tas.comparaisons;
}

Exemple pas à pas : les liaisons des huit villages

Les onze liaisons possibles entre les huit villages ont les coûts de la figure de la section 1. Le programme construit l’arbre couvrant de coût minimal, avec la classe PathCompressionUF.

var tas = new BinaryMinHeap<Arete>();
for (Arete e : g.aretes()) tas.insert(e);
var uf = new PathCompressionUF(g.V());
while (arbre.size() < g.V() - 1) {
    Arete e = tas.extractMin();
    if (uf.connected(e.v, e.w)) continue;
    uf.union(e.v, e.w);
    arbre.add(e);
    poids += e.poids;
    System.out.print(e.poids + " ");
}
System.out.println("total " + poids);
Étape Lignes Instruction Effet Écrit
1 1–3 tas des aretes ; uf Les 11 liaisons entrent dans le tas ; huit composantes.
2 4–10 extractMin() : 4-5 9 4–5 (9) : racines 4 et 5, 5 passe sous 4.
3 4–10 extractMin() : 6-7 11 6–7 (11) : racines 6 et 7, 7 passe sous 6.
4 4–10 extractMin() : 0-1 12 0–1 (12) : racines 0 et 1, 1 passe sous 0.
5 4–10 extractMin() : 0-2 14 0–2 (14) : racines 0 et 2, 2 passe sous 0.
6 4–10 extractMin() : 2-3 15 2–3 (15) : racines 0 et 3, 3 passe sous 0.
7 4–10 extractMin() : 0-6 16 0–6 (16) : racines 0 et 6, 6 passe sous 0.
8 4–6 extractMin() : 1-2 18 1–2 (18) : find rend 0 pour les deux, rejetée.
9 4–6 extractMin() : 2-6 20 2–6 (20) : find rend 0 pour les deux, rejetée.
10 4–10 extractMin() : 4-7 22 4–7 (22) : find(7) rattache 7 à 0 (compression), puis 4 passe sous 0.
11 12 println("total " + poids) 99 millions de FCFA ; 9 liaisons examinées, 2 rejetées par find, sans parcours. total 99

Les six premières liaisons sorties du tas sont gardées : chacune relie deux composantes distinctes. À l’étape 8, Saly–Malicounda (18) est rejetée : find(1) et find(2) rendent tous deux 0, Saly et Malicounda étant déjà reliées par Mbour. Malicounda–Nianing (20) est rejetée pour la même raison. À l’étape 10, Joal–Pointe Sarène (22) relie la composante de Joal et Fadial à celle de tous les autres villages : find(7) suit 7, 6, 0 et rattache 7 directement à 0 par compression, puis l’union place la racine 4, d’un arbre de taille 2, sous la racine 0, d’un arbre de taille 6.


Étape 8 : Saly–Malicounda rejetée


Étape 10 : compression, puis union

Sortie \(\rightarrow\)

9 11 12 14 15 16 22 
total 99

Le réseau coûte 99 millions de FCFA ; les deux liaisons rejetées n’ont demandé que deux find chacune.

Le gain mesuré

Le programme suivant reprend les graphes au hasard de la Séance 5 (même générateur, même graine 221, \(E=4V\)) et lance les deux versions de Kruskal sur chacun.

Random r = new Random(221);                // les graphes de la Seance 5
for (int V : new int[] {500, 1000, 2000, 4000}) {
    GraphePondere g = new GraphePondere(V, false);
    for (int[] a : Generateur.aretes(V, 4 * V, r)) g.addEdge(a[0], a[1], a[2]);
    Kruskal k = new Kruskal(g);            // test de cycle par parcours
    KruskalUF u = new KruskalUF(g);        // test de cycle par union-find
    System.out.printf(Locale.ROOT, "%4d : %5d examinees ; parcours %8d visites ; "
        + "union-find %6d acces%n", V, u.examinees, k.visites, u.acces());
}

Sortie \(\rightarrow\)

 500 :  1718 examinees ; parcours   611838 visites ; union-find  19301 acces
1000 :  2971 examinees ; parcours  1986671 visites ; union-find  33723 acces
2000 :  5681 examinees ; parcours  7389527 visites ; union-find  65343 acces
4000 : 13589 examinees ; parcours 38476757 visites ; union-find 152747 acces

Les deux versions examinent les mêmes arêtes, dans le même ordre, et construisent le même arbre. Le test par parcours atteint \(611\,838\) sommets pour \(V=500\) et \(38\,476\,757\) pour \(V=4\,000\) : il est multiplié par 3,2 à 5,2 quand \(V\) double. Union-find fait \(19\,301\) puis \(152\,747\) accès : environ 11 accès par arête examinée, quel que soit \(V\), et 252 fois moins d’opérations pour \(V=4\,000\). Le coût de Kruskal se ramène à celui du tas des arêtes, \(\mathcal{O}(E\log E)\).

Le tri par insertion

Les quatre tris de la séance sont des tris par comparaison : ils n’apprennent rien des clés autrement qu’en les comparant deux à deux par compareTo. Ils héritent de la classe Tri, qui compte les comparaisons et les accès au tableau.

public long comparaisons;  // appels de plusPetit
public long acces;         // acces au tableau

public abstract void trier(K[] a);

protected boolean plusPetit(K[] a, int i, int j) {
    comparaisons++;
    acces += 2;
    return a[i].compareTo(a[j]) < 0;
}

protected void echanger(K[] a, int i, int j) {
    K t = a[i];
    a[i] = a[j];
    a[j] = t;
    acces += 4;
}
NoteTri en place, tri stable

Un tri est en place s’il n’utilise qu’une mémoire auxiliaire de taille constante (hors pile des appels). Il est stable si deux éléments de clés égales sortent dans leur ordre de départ : un classement d’étudiants par note, à partir d’une liste alphabétique, garde alors l’ordre alphabétique entre deux notes égales.

Le tri par insertion trie un tableau comme on range des copies une à une dans un paquet déjà ordonné. Avant le tour \(i\), la partie a[0..i-1] est triée ; l’élément a[i] recule alors par échanges successifs tant qu’il est strictement plus petit que son voisin de gauche.

@Override
public void trier(K[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0 && plusPetit(a, j, j - 1); j--) {
            echanger(a, j, j - 1);  // a[j] recule d'une case
        }
    }
}

Une inversion est une paire d’indices \(i<j\) avec \(a[i]>a[j]\). Chaque échange de deux voisins mal ordonnés supprime exactement une inversion, et le tri s’arrête quand il n’en reste aucune : le nombre d’échanges est égal au nombre d’inversions du tableau de départ. Le nombre de comparaisons vaut le nombre d’échanges, plus une comparaison par tour qui s’arrête sur un voisin plus petit ou égal. La comparaison étant stricte, un élément ne passe jamais devant un élément de même clé : le tri est stable. Il est en place.

Exemple pas à pas : six prix au marché

int[] a = {650, 300, 900, 150, 500, 700};
for (int i = 1; i < a.length; i++) {
    for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
        int t = a[j];
        a[j] = a[j - 1];
        a[j - 1] = t;
    }
}
System.out.println(Arrays.toString(a));
Étape Lignes Instruction Effet Écrit
1 1 int[] a = {...} Six prix relevés au marché, en FCFA ; la partie triée, en jaune, commence par la case 0.
2 2–6 i = 1, j = 1 \(i=1\), \(j=1\) : 300 \(<\) 650 : échange, 300 recule en case 0. \(j=0\) : la boucle s’arrête sans comparer.
3 2–3 i = 2, j = 2 \(i=2\), \(j=2\) : 900 \(\geq\) 650 : une comparaison place 900.
4 2–6 i = 3, j = 3 \(i=3\), \(j=3\) : 150 \(<\) 900 : échange, 150 recule en case 2.
5 3–6 i = 3, j = 2 \(i=3\), \(j=2\) : 150 \(<\) 650 : échange, 150 recule en case 1.
6 3–6 i = 3, j = 1 \(i=3\), \(j=1\) : 150 \(<\) 300 : échange, 150 recule en case 0. \(j=0\) : la boucle s’arrête sans comparer.
7 2–6 i = 4, j = 4 \(i=4\), \(j=4\) : 500 \(<\) 900 : échange, 500 recule en case 3.
8 3–6 i = 4, j = 3 \(i=4\), \(j=3\) : 500 \(<\) 650 : échange, 500 recule en case 2.
9 3 i = 4, j = 2 \(i=4\), \(j=2\) : 500 \(\geq\) 300 : la boucle s’arrête, 500 est à sa place.
10 2–6 i = 5, j = 5 \(i=5\), \(j=5\) : 700 \(<\) 900 : échange, 700 recule en case 4.
11 3 i = 5, j = 4 \(i=5\), \(j=4\) : 700 \(\geq\) 650 : la boucle s’arrête, 700 est à sa place.
12 9 println(Arrays.toString(a)) 10 comparaisons, 7 échanges : un échange par inversion du tableau de départ. [150, 300, 500, 650, 700, 900]

Le tour \(i=2\) ne coûte qu’une comparaison : 900 est plus grand que 650, il est déjà à sa place. Le tour \(i=3\) fait reculer 150 jusqu’en case 0, en trois échanges ; la boucle s’arrête alors sur \(j=0\) sans comparaison. Les 7 échanges correspondent aux 7 inversions du tableau de départ : (650, 300), (650, 150), (650, 500), (300, 150), (900, 150), (900, 500), (900, 700).


Étape 6 : 150 arrive en case 0


Étape 12 : le tableau trié

Sortie \(\rightarrow\)

[150, 300, 500, 650, 700, 900]

Le coût selon l’ordre de départ

Le programme suivant compte les comparaisons sur un tableau croissant, un tableau au hasard et un tableau décroissant, puis écrit \(n^2/4\).

Random r = new Random(2026);
for (int n : new int[] {1000, 2000, 4000}) {
    Integer[][] cas = {Donnees.croissant(n), Donnees.auHasard(n, r),
        Donnees.decroissant(n)};
    System.out.printf("%4d", n);
    for (Integer[] a : cas) {
        TriInsertion<Integer> t = new TriInsertion<>();
        t.trier(a);
        System.out.printf(" %11d", t.comparaisons);
    }
    System.out.printf(" %9d%n", n * n / 4);
}

Sortie \(\rightarrow\)

1000         999      251591      499500    250000
2000        1999      997770     1999000   1000000
4000        3999     3999750     7998000   4000000

Un tableau croissant n’a aucune inversion : chaque tour fait une comparaison, \(n-1\) au total. Un tableau décroissant a toutes ses paires inversées, \(n(n-1)/2\) : \(7\,998\,000\) comparaisons pour \(n=4\,000\). Au hasard, chaque paire est inversée avec probabilité \(1/2\) : l’espérance du nombre d’inversions est \(n(n-1)/4\), et la mesure donne \(3\,999\,750\) comparaisons pour \(n=4\,000\), près de \(n^2/4=4\,000\,000\). Le tri par insertion est quadratique en moyenne, mais linéaire sur un tableau presque trié : il convient aux petits tableaux et aux tableaux où chaque élément est proche de sa place.

Le tri fusion

Le tri fusion applique la méthode « diviser pour régner » de la Séance 2 : trier chaque moitié par un appel récursif, puis fusionner les deux moitiés triées. La récursion s’arrête aux sous-tableaux d’un élément, qui sont triés. Le tableau auxiliaire aux, de \(n\) cases, est alloué une fois par la méthode publique ; le tri fusion n’est pas en place.

@Override
public void trier(K[] a) {
    K[] aux = Arrays.copyOf(a, a.length);
    trier(a, aux, 0, a.length - 1);
}

private void trier(K[] a, K[] aux, int lo, int hi) {
    if (hi <= lo) return;              // 0 ou 1 element
    int mid = lo + (hi - lo) / 2;
    trier(a, aux, lo, mid);            // moitie gauche
    trier(a, aux, mid + 1, hi);        // moitie droite
    fusionner(a, aux, lo, mid, hi);
}

La fusion copie a[lo..hi] dans aux, puis remplit a[lo..hi] case par case : \(i\) parcourt la moitié gauche, \(j\) la moitié droite, et chaque case reçoit la plus petite des deux têtes, ou le reste de la moitié qui n’est pas épuisée.

private void fusionner(K[] a, K[] aux, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) aux[k] = a[k];
    acces += 2L * (hi - lo + 1);
    int i = lo;                        // tete de la moitie gauche
    int j = mid + 1;                   // tete de la moitie droite
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (plusPetit(aux, j, i)) a[k] = aux[j++];
        else a[k] = aux[i++];          // egalite : la gauche d'abord
        acces += 2;
    }
}

La comparaison plusPetit(aux, j, i) est stricte : à égalité, c’est la tête de gauche qui est copiée. Deux éléments égaux restent ainsi dans leur ordre de départ ; le tri fusion est stable.

Exemple pas à pas : la fusion de deux moitiés triées

Les deux moitiés 200 450 600 850 et 150 450 500 900 sont triées ; la fusion les réunit.

static void fusionner(int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) aux[k] = a[k];
    int i = lo;
    int j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (aux[j] < aux[i]) a[k] = aux[j++];
        else a[k] = aux[i++];
    }
}
// dans main :
fusionner(0, 3, 7);
System.out.println(Arrays.toString(a));
Étape Lignes Instruction Effet Écrit
1 2, 13 fusionner(0, 3, 7) ; copie dans aux fusionner(0, 3, 7) : les deux moitiés triées sont copiées dans aux, la gauche en bleu, la droite en orange.
2 3–4 i = lo ; j = mid + 1 \(i\) pointe la tête de la moitié gauche, \(j\) celle de la droite.
3 5, 8 k = 0 \(k=0\) : 150 \(<\) 200 : a[0] reçoit 150, de la droite, et \(j\) avance.
4 5, 9 k = 1 \(k=1\) : 450 \(\geq\) 200 : a[1] reçoit 200, de la gauche, et \(i\) avance.
5 5, 9 k = 2 \(k=2\) : égalité, 450 et 450 : la gauche passe d’abord. C’est ce qui rend le tri stable.
6 5, 8 k = 3 \(k=3\) : 450 \(<\) 600 : a[3] reçoit 450, de la droite, et \(j\) avance.
7 5, 8 k = 4 \(k=4\) : 500 \(<\) 600 : a[4] reçoit 500, de la droite, et \(j\) avance.
8 5, 9 k = 5 \(k=5\) : 900 \(\geq\) 600 : a[5] reçoit 600, de la gauche, et \(i\) avance.
9 5, 9 k = 6 \(k=6\) : 900 \(\geq\) 850 : a[6] reçoit 850, de la gauche, et \(i\) avance.
10 5–6 k = 7 \(k=7\) : \(i>\) mid, la gauche est épuisée : a[7] reçoit 900.
11 14 println(Arrays.toString(a)) 8 cases écrites, 7 comparaisons : une fusion de \(n\) éléments compare au plus \(n-1\) fois. [150, 200, 450, 450, 500, 600, 850, 900]

À l’étape 5, les deux têtes valent 450 : la gauche passe d’abord, et le 450 de gauche précède celui de droite dans le résultat. À l’étape 10, \(i\) a dépassé mid : la moitié gauche est épuisée, et 900 est copié sans comparaison. La fusion de 8 éléments a fait 7 comparaisons : une fusion de \(n\) éléments en fait au plus \(n-1\), et au moins \(\min(n_1, n_2)\), la taille de la plus petite moitié.


Étape 6 : 450 de droite, en case 3


Étape 11 : le tableau fusionné

Sortie \(\rightarrow\)

[150, 200, 450, 450, 500, 600, 850, 900]

Le coût du tri fusion

Les deux moitiés de l’exemple viennent du tableau 600 200 850 450 150 900 450 500, trié par le tri fusion : la figure montre le tableau après chaque niveau de fusions.

Chaque niveau fusionne des sous-tableaux deux fois plus longs que le précédent, et compare au plus \(n-1\) fois. Le nombre \(C(n)\) de comparaisons vérifie \(C(n)\leq C(\lceil n/2\rceil)+C(\lfloor n/2\rfloor)+n-1\), avec \(C(1)=0\). Pour \(n=2^k\), l’arbre des appels a \(k=\log_2 n\) niveaux, d’où \(C(n)\leq n\log_2 n\) ; en général \(C(n)\leq n\lceil\log_2 n\rceil\). Le théorème maître de la Séance 2 (\(a=b=2\), travail \(\Theta(n)\) par appel) donne un coût \(\Theta(n\log n)\), quel que soit l’ordre de départ : même un tableau trié est fusionné niveau par niveau. Ici, \(4+6+7=17\) comparaisons pour \(n=8\), le pire cas pour cette taille.

Le tri rapide

Le tri rapide (Hoare, 1962) divise lui aussi le tableau en deux, mais autour d’une valeur, le pivot : la partition place à gauche les éléments plus petits que le pivot, à droite les autres, et le pivot entre les deux, à sa place définitive. Il reste à trier les deux côtés, sans fusion.

@Override
public void trier(K[] a) {
    trier(a, 0, a.length - 1);
}

private void trier(K[] a, int lo, int hi) {
    if (lo >= hi) return;  // 0 ou 1 element
    int p = partition(a, lo, hi);
    trier(a, lo, p - 1);
    trier(a, p + 1, hi);
}
public int partition(K[] a, int lo, int hi) {
    int r = lo + hasard.nextInt(hi - lo + 1);
    echanger(a, r, hi);  // le pivot en a[hi]
    int i = lo;          // a[lo..i-1] < pivot
    for (int j = lo; j < hi; j++) {
        if (plusPetit(a, j, hi)) {
            echanger(a, i, j);
            i++;
        }
    }
    echanger(a, i, hi);  // le pivot a sa place
    return i;
}
NotePartition de Lomuto, pivot aléatoire

Le cours utilise la partition de Lomuto (CLRS, § 7.1). Le pivot est placé en a[hi] ; l’indice \(j\) parcourt a[lo..hi-1], et l’indice \(i\) marque la fin de la zone des éléments strictement plus petits que le pivot. Quand a[j] est plus petit que le pivot, il est échangé avec a[i], et \(i\) avance. À la fin, le pivot est échangé avec a[i]. Le pivot est tiré au hasard dans a[lo..hi] par hasard.nextInt(hi - lo + 1) (pivot aléatoire, CLRS, § 7.3).

L’invariant de la boucle est le suivant : avant le tour \(j\), a[lo..i-1] contient des éléments strictement plus petits que le pivot, et a[i..j-1] des éléments plus grands ou égaux. Chaque tour fait une comparaison : une partition de \(m\) éléments compare \(m-1\) fois.

Exemple pas à pas : huit prix autour d’un pivot

static int partition(int lo, int hi) {
    int r = lo + hasard.nextInt(hi - lo + 1);
    echanger(r, hi);
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < a[hi]) {
            echanger(i, j);
            i++;
        }
    }
    echanger(i, hi);
    return i;
}
// dans main :
System.out.println(partition(0, 7));
Étape Lignes Instruction Effet Écrit
1 2, 15 r = lo + hasard.nextInt(8) partition(0, 7) : hasard (graine 2026) tire \(r=4\) ; le pivot est 600.
2 3 echanger(r, hi) Le pivot 600 passe en case 7, la dernière ; 300 prend sa place.
3 4 i = lo \(i=0\) : la zone des éléments plus petits que le pivot est vide.
4 5–6 j = 0 : a[j] < a[hi] ? \(j=0\) : 750 \(\geq\) 600 : il reste dans la zone de droite, \(i\) ne bouge pas.
5 5–8 j = 1 : a[j] < a[hi] ? \(j=1\) : 250 \(<\) 600 : échange des cases 0 et 1, puis \(i=1\).
6 5–6 j = 2 : a[j] < a[hi] ? \(j=2\) : 950 \(\geq\) 600 : il reste dans la zone de droite, \(i\) ne bouge pas.
7 5–8 j = 3 : a[j] < a[hi] ? \(j=3\) : 400 \(<\) 600 : échange des cases 1 et 3, puis \(i=2\).
8 5–8 j = 4 : a[j] < a[hi] ? \(j=4\) : 300 \(<\) 600 : échange des cases 2 et 4, puis \(i=3\).
9 5–8 j = 5 : a[j] < a[hi] ? \(j=5\) : 100 \(<\) 600 : échange des cases 3 et 5, puis \(i=4\).
10 5–6 j = 6 : a[j] < a[hi] ? \(j=6\) : 850 \(\geq\) 600 : il reste dans la zone de droite, \(i\) ne bouge pas.
11 11 echanger(i, hi) Le pivot passe en case 4 : à sa gauche les 4 prix plus petits, à sa droite les 3 plus grands.
12 12, 15 return i ; println partition rend 4 : 7 comparaisons. Le tri rapide trie ensuite a[0..3] et a[5..7]. 4

Le générateur, de graine 2026, tire \(r=4\) : le pivot est 600, échangé avec 300 en case 7. Les éléments 250, 400, 300 et 100 sont plus petits ; chacun est échangé avec la première case de la zone de droite, puis \(i\) avance. Les éléments 750, 950 et 850 restent dans la zone de droite. À la fin, le pivot est échangé avec a[4] : à sa gauche les 4 prix plus petits, à sa droite les 3 plus grands, chacun encore dans le désordre.


Étape 7 : \(j=3\), 400 passe à gauche


Étape 11 : le pivot à sa place

Sortie \(\rightarrow\)

4

Coût moyen et pire cas

Si chaque partition coupait le tableau en deux moitiés, le coût serait celui du tri fusion. Avec un pivot tiré au hasard et des clés distinctes, le nombre moyen de comparaisons vaut \(2(n+1)H_n-4n\), où \(H_n=1+\frac12+\dots+\frac1n\) ; c’est environ \(2n\ln n\approx1{,}39\,n\log_2 n\) pour \(n\) grand (CLRS, § 7.4 ; Sedgewick et Wayne, § 2.3, proposition K). Pour \(n=1\,024\,000\), cette moyenne vaut \(25\,428\,905\) ; la classe du cours en a fait \(25\,033\,925\). Le hasard porte sur les tirages du pivot, pas sur l’ordre des données : un tableau déjà trié n’est pas un pire cas, contrairement au tri rapide qui prend toujours a[hi] comme pivot.

Le pire cas reste \(n(n-1)/2\) comparaisons, quand chaque partition ne détache que le pivot. Il devient certain lorsque toutes les clés sont égales : aucun élément n’est strictement plus petit que le pivot, et chaque partition rend lo.

for (int n : new int[] {1000, 2000, 4000}) {
    Integer[] a = new Integer[n];
    Arrays.fill(a, 500);                    // n prix identiques
    TriRapide<Integer> t = new TriRapide<>(2026);
    t.trier(a);
    System.out.println(n + " : " + t.comparaisons + " comparaisons ; n(n-1)/2 = "
        + n * (n - 1) / 2);
}

Sortie \(\rightarrow\)

1000 : 499500 comparaisons ; n(n-1)/2 = 499500
2000 : 1999000 comparaisons ; n(n-1)/2 = 1999000
4000 : 7998000 comparaisons ; n(n-1)/2 = 7998000

Chaque appel ne trie qu’un élément de moins que son appelant : \(n\) appels sont imbriqués, et la pile des appels grandit avec \(n\), au risque de StackOverflowError pour de grandes valeurs. La partition en trois zones (inférieurs, égaux, supérieurs) de Sedgewick et Wayne (§ 2.3) écarte ce cas.

Stabilité

Les échanges de la partition déplacent des éléments à longue distance : un élément peut passer devant un autre de même clé. Le programme suivant classe six étudiants, donnés par ordre alphabétique, par note décroissante (compareTo de la classe Etudiant).

@Override
public int compareTo(Etudiant o) {
    return Integer.compare(o.note, note);  // meilleure note d'abord
}
Etudiant[] liste = {new Etudiant("Awa", 14), new Etudiant("Cheikh", 12),
    new Etudiant("Coumba", 15), new Etudiant("Fatou", 12),
    new Etudiant("Moussa", 14), new Etudiant("Ndeye", 12)};  // ordre alphabetique
Etudiant[] f = liste.clone();
new TriFusion<Etudiant>().trier(f);
System.out.println("fusion : " + Arrays.toString(f));
Etudiant[] q = liste.clone();
new TriRapide<Etudiant>(2026).trier(q);
System.out.println("rapide : " + Arrays.toString(q));

Sortie \(\rightarrow\)

fusion : [Coumba 15, Awa 14, Moussa 14, Cheikh 12, Fatou 12, Ndeye 12]
rapide : [Coumba 15, Awa 14, Moussa 14, Ndeye 12, Cheikh 12, Fatou 12]

Le tri fusion garde Cheikh, Fatou et Ndeye, trois notes de 12, dans l’ordre alphabétique ; le tri rapide les rend dans l’ordre Ndeye, Cheikh, Fatou. Le tri rapide et le tri par tas ne sont pas stables ; le tri par insertion et le tri fusion le sont.

La borne inférieure des tris par comparaison

Le tri fusion fait \(\Theta(n\log n)\) comparaisons ; aucun tri par comparaison ne peut faire mieux, à un facteur constant près. L’argument représente le tri par un arbre.

NoteArbre de décision

Pour une taille \(n\) fixée, un tri par comparaison se représente par un arbre de décision : un arbre binaire dont chaque nœud interne est une comparaison entre deux éléments, avec une branche par résultat, et dont chaque feuille est un ordre de sortie. Une exécution sur des données particulières suit un chemin de la racine à une feuille ; la longueur du chemin est le nombre de comparaisons, et la hauteur de l’arbre est le nombre de comparaisons au pire.

L’arbre du tri par insertion sur trois éléments \(a\), \(b\), \(c\) a été obtenu en exécutant le tri sur les six ordres possibles et en relevant ses comparaisons :

Il a 6 feuilles, une par ordre, et une hauteur de 3 : 2 comparaisons pour les ordres \(b<a<c\) et \(a<b<c\), 3 pour les quatre autres.

NoteThéorème (CLRS, § 8.1 ; Sedgewick et Wayne, § 2.2)

Tout tri par comparaison fait au moins \(\lceil\log_2 n!\rceil\) comparaisons au pire pour trier \(n\) éléments distincts.

Les \(n!\) permutations des données doivent mener à \(n!\) feuilles distinctes : deux permutations différentes demandent deux réarrangements différents. Un arbre binaire de hauteur \(h\) a au plus \(2^h\) feuilles ; il faut donc \(2^h\geq n!\), soit \(h\geq\log_2 n!\). Pour l’ordre de grandeur, les \(n/2\) plus grands facteurs de \(n!\) sont au moins égaux à \(n/2\) : \[\log_2 n!\;\geq\;\log_2\Big(\big(\tfrac n2\big)^{n/2}\Big)=\tfrac n2\log_2\tfrac n2=\Omega(n\log n),\] et la formule de Stirling précise \(\log_2 n!=n\log_2 n-n\log_2 e+\mathcal{O}(\log n)\), avec \(\log_2 e\approx1{,}44\). Le tri fusion, en \(n\lceil\log_2 n\rceil\) au pire, est donc optimal à un facteur constant près. Un algorithme qui ne compare pas échappe à la borne : le tri par dénombrement (CLRS, § 8.2) compte les occurrences de clés entières d’un intervalle connu.

Les tris côte à côte

Les quatre classes ont trié les mêmes tableaux d’entiers au hasard (Random(2026)), de \(1\,000\) à \(1\,024\,000\) éléments (\(16\,000\) au plus pour le tri par insertion). La figure de gauche donne les comparaisons, celle de droite leur rapport à \(n\log_2 n\), avec la borne \(\log_2 n!\).

tri pire cas moyenne mesuré, \(n=1\,024\,000\) mémoire stable
insertion \(n(n-1)/2\) \(\approx n^2/4\) \(0{,}25\,n^2\) (à \(n=16\,000\)) en place oui
fusion \(\leq n\lceil\log_2 n\rceil\) \(\Theta(n\log n)\) \(0{,}94\,n\log_2 n\) tableau aux de \(n\) cases oui
rapide \(n(n-1)/2\) \(\approx1{,}39\,n\log_2 n\) (1,24 à cette taille) \(1{,}22\,n\log_2 n\) en place, pile des appels non
tas (Séance 4) \(\mathcal{O}(n\log n)\) \(\Theta(n\log n)\) \(1{,}87\,n\log_2 n\) tas de \(n\) éléments non
borne \(\lceil\log_2 n!\rceil\) \(0{,}93\,n\log_2 n\)

Le tri fusion fait \(19\,154\,251\) comparaisons pour \(n=1\,024\,000\), à 1 % de la borne \(\log_2 n!\approx18\,967\,655\). Le tri rapide en fait 31 % de plus, mais il est en place et ses accès au tableau sont moins nombreux (\(103\,733\,826\) contre \(120\,130\,198\) pour le tri fusion, qui recopie chaque sous-tableau dans aux). Le tri par tas de la Séance 4, avec \(n\) insertions puis \(n\) extractions dans un tas séparé, fait près de deux fois la borne : chaque extraction compare deux fois par niveau. Le tri par insertion n’est compétitif que sur de petits tableaux ou des tableaux presque triés.

Exercices corrigés

Les trois exercices reprennent les raisonnements des sections précédentes sur des données nouvelles ; ils préparent le TD (tableaux à remplir après chaque opération) et le TP (compteurs des classes du cours).

Exercice 1 : trois versions d’union-find sur la même suite

Neuf éléments, numérotés de 0 à 8, reçoivent dans cet ordre les unions union(8, 7), union(7, 6), union(6, 5), union(0, 1), union(2, 3), union(1, 3), union(5, 3), union(4, 8), union(2, 0).

  1. Avec QuickUnion, donner parent[] après chaque union et le nombre d’accès de chaque appel, puis la hauteur finale.
  2. Avec l’union pondérée par la taille, donner parent[], la taille de la racine qui reçoit l’autre, les accès, et la hauteur finale.
  3. Avec la compression de chemin en plus, dire quelles unions modifient parent[] au-delà du lien entre les racines.
  4. Dans la dernière forêt, dérouler find(3) : chemin, accès, parent[] après.
AstuceCorrection

(a) Règle : union(p, q) cherche les racines \(i\) de \(p\) et \(j\) de \(q\) et place \(i\) sous \(j\) ; un find de profondeur \(d\) coûte \(2d+1\) accès, l’écriture 1. Les cases modifiées sont en rouge.

union QuickUnion acc. pondérée taille acc. compression (acc.)
(8, 7) 0 1 2 3 4 5 6 7 7 3 0 1 2 3 4 5 6 8 8 t[8] \(=2\) 3 comme pondérée (3)
(7, 6) 0 1 2 3 4 5 6 6 7 3 0 1 2 3 4 5 8 8 8 t[8] \(=3\) 5 comme pondérée (7)
(6, 5) 0 1 2 3 4 5 5 6 7 3 0 1 2 3 4 8 8 8 8 t[8] \(=4\) 5 comme pondérée (7)
(0, 1) 1 1 2 3 4 5 5 6 7 3 0 0 2 3 4 8 8 8 8 t[0] \(=2\) 3 comme pondérée (3)
(2, 3) 1 1 3 3 4 5 5 6 7 3 0 0 2 2 4 8 8 8 8 t[2] \(=2\) 3 comme pondérée (3)
(1, 3) 1 3 3 3 4 5 5 6 7 3 0 0 0 2 4 8 8 8 8 t[0] \(=4\) 7 comme pondérée (11)
(5, 3) 1 3 3 3 4 3 5 6 7 3 8 0 0 2 4 8 8 8 8 t[8] \(=8\) 9 8 0 0 0 4 8 8 8 8 (15)
(4, 8) 1 3 3 3 3 3 5 6 7 11 8 0 0 2 8 8 8 8 8 t[8] \(=9\) 3 8 0 0 0 8 8 8 8 8 (3)
(2, 0) 1 3 3 3 3 3 5 6 7 8 8 0 0 2 8 8 8 8 8 — 8 8 0 8 0 8 8 8 8 8 (14)

Les trois premières unions construisent la chaîne 8, 7, 6, 5 : la racine du premier argument est toujours l’ancienne racine de la chaîne, et elle passe sous un élément isolé. union(5, 3) accroche cette chaîne sous 3, et union(4, 8) doit remonter de 8 à 3, soit 4 liens et 9 accès pour find(8), plus 1 pour find(4) et 1 pour l’écriture : 11. union(2, 0) trouve la même racine 3 pour les deux éléments : elle ne modifie rien, mais coûte 8 accès. La hauteur finale est 4, atteinte par 8 (8, 7, 6, 5, 3) ; 40 accès au total.

(b) Règle : la racine du plus petit arbre passe sous celle du plus grand ; à égalité, la racine de \(q\) passe sous celle de \(p\). Avec union(8, 7), deux arbres de taille 1 : 7 passe sous 8. Les deux unions suivantes ajoutent 6 puis 5 sous 8, dont l’arbre est le plus grand : la chaîne de QuickUnion devient une étoile. union(1, 3) réunit deux arbres de taille 2 (racines 0 et 2) : 2 passe sous 0. union(5, 3) réunit deux arbres de taille 4 (racines 8 et 0) : 0 passe sous 8, et l’élément 3 se trouve au bout du chemin 3, 2, 0, 8. La hauteur finale est 3, au plus \(\log_2 9\approx3{,}17\) ; 46 accès au total.

(c) La compression ne change parent[] que lorsqu’un find parcourt au moins deux liens. Pendant union(5, 3), find(3) suit 3, 2, 0 et rattache 3 à 0 avant l’union ; pendant union(2, 0), find(2) suit 2, 0, 8 et rattache 2 à 8. Toutes les autres unions donnent le même tableau que l’union pondérée. La hauteur finale est 2. Sur une suite aussi courte, les écritures du second passage coûtent plus qu’elles ne rapportent (66 accès contre 46) : l’avantage de la compression n’apparaît que sur de longues suites d’opérations.

(d) parent[3] vaut 0 et parent[0] vaut 8 : chemin 3, 0, 8, de profondeur 2. Le premier passage coûte \(2\times2+1=5\) accès, le second \(2\times2=4\) (les éléments 3 et 0 sont réécrits) : 9 accès. Après l’appel, parent \(=\) [8, 0, 8, 8, 8, 8, 8, 8, 8] : tous les éléments sauf 1 sont fils de la racine.

Erreur fréquente : placer sous l’autre l’élément \(p\) au lieu de sa racine. Avec parent[p] = j, l’ancien parent de \(p\) et ses autres descendants resteraient dans l’ancien arbre, et la composante serait coupée en deux.

Exercice 2 : un tri rapide complet

Le tableau a = [62, 18, 47, 90, 25, 71, 36, 54] est trié par new TriRapide<Integer>(54).trier(a). Les tirages successifs du pivot donnent \(r=5\), puis \(5\), \(0\) et \(4\).

  1. Pour chaque appel de partition : le sous-tableau, le pivot, le nombre de comparaisons, le tableau après la partition et la valeur rendue.
  2. Le nombre total de comparaisons et la profondeur des appels.
  3. Comparer au nombre de comparaisons d’une partition parfaite à chaque appel.
AstuceCorrection

(a) Règle : partition(a, lo, hi) échange le pivot a[r] avec a[hi], compare chaque a[j], \(j\) de lo à hi-1, au pivot, échange les plus petits avec a[i] et avance \(i\), puis place le pivot en a[i]. Le pivot placé est en rouge.

appel tirage \(r\) pivot comparaisons tableau après la partition rendu \(p\)
a[0..7] 5 71 7 62 18 47 25 54 36 71 90 6
a[0..5] 5 36 5 18 25 36 62 54 47 71 90 2
a[0..1] 0 18 1 18 25 36 62 54 47 71 90 0
a[3..5] 4 54 2 18 25 36 47 54 62 71 90 4

Premier appel : le pivot 71 (case 5) est le deuxième plus grand élément ; seul 90 est plus grand, et la partition rend 6. Deuxième appel, sur a[0..5] \(=\) 62 18 47 25 54 36 : le pivot est 36, case 5, et deux éléments sont plus petits (18, 25), d’où \(p=2\). Le troisième appel trie a[0..1] autour de 18 : 25 n’est pas plus petit, \(p=0\). L’appel sur a[1..1] s’arrête sans partition (un élément), de même que a[3..2], vide. Le quatrième appel trie a[3..5] \(=\) 62 54 47 autour de 54 : 47 passe à gauche, \(p=4\). Le côté droit du premier appel, a[7..7], n’a qu’un élément.

(b) \(7+5+1+2=15\) comparaisons ; le plus long enchaînement d’appels va de a[0..7] à a[0..5], a[3..5], puis à un sous-tableau d’un élément : profondeur 4.

(c) Une partition de \(m\) éléments coûte toujours \(m-1\) comparaisons ; seul le partage varie. Avec des pivots médians, les appels porteraient sur 8, puis deux fois 3 ou 4 éléments, etc., pour 13 comparaisons au plus ; le premier pivot, mal placé, ne détache que 90, et le second appel porte encore sur 6 éléments. Le tri par insertion sur ce tableau ferait 19 comparaisons (13 inversions), et la borne vaut \(\lceil\log_2 8!\rceil=16\) au pire : un tri rapide peut passer sous la borne sur des données particulières, la borne ne portant que sur le pire cas.

Erreur fréquente : oublier que le pivot est d’abord placé en a[hi]. Le tableau après la partition se lit alors faussement, et le pivot ne finit pas à l’indice rendu.

Exercice 3 : les comparaisons de deux tris stables

Huit prix, en FCFA, sont donnés dans cet ordre : 40, 15, 40, 25, 10, 35, 20, 30 ; le premier 40 est noté \(40_a\), le second \(40_b\).

  1. Trier le tableau par insertion : le tableau après chaque tour, les comparaisons et les échanges.
  2. Trier le tableau par fusion : chaque appel de fusionner, le sous-tableau obtenu et ses comparaisons.
  3. Comparer les deux totaux à \(\lceil\log_2 8!\rceil\). Les deux tris gardent-ils \(40_a\) devant \(40_b\) ?
AstuceCorrection

(a) Règle : au tour \(i\), a[i] recule tant qu’il est strictement plus petit que son voisin de gauche ; chaque échange supprime une inversion.

tour tableau après le tour comparaisons échanges
\(i=1\) 15 40 40 25 10 35 20 30 1 1
\(i=2\) 15 40 40 25 10 35 20 30 1 0
\(i=3\) 15 25 40 40 10 35 20 30 3 2
\(i=4\) 10 15 25 40 40 35 20 30 4 4
\(i=5\) 10 15 25 35 40 40 20 30 3 2
\(i=6\) 10 15 20 25 35 40 40 30 5 4
\(i=7\) 10 15 20 25 30 35 40 40 4 3
total 21 16

Au tour \(i=2\), \(40_b\) est comparé à \(40_a\) : \(40<40\) est faux, \(40_b\) reste derrière. Au tour \(i=4\), 10 recule jusqu’en case 0 en 4 échanges ; la boucle s’arrête sur \(j=0\), sans cinquième comparaison. Le tableau de départ compte 16 inversions, autant que d’échanges ; les 21 comparaisons sont les 16 comparaisons suivies d’un échange et 5 comparaisons d’arrêt (tours 2, 3, 5, 6 et 7).

(b) Règle : trier(lo, hi) trie a[lo..mid] et a[mid+1..hi], avec \(\texttt{mid}=\texttt{lo}+(\texttt{hi}-\texttt{lo})/2\), puis fusionne ; une fusion s’arrête de comparer dès qu’une moitié est épuisée.

fusion sous-tableau après comparaisons
fusionner(0, 0, 1) 15 40 1
fusionner(2, 2, 3) 25 40 1
fusionner(0, 1, 3) 15 25 40 40 3
fusionner(4, 4, 5) 10 35 1
fusionner(6, 6, 7) 20 30 1
fusionner(4, 5, 7) 10 20 30 35 3
fusionner(0, 3, 7) 10 15 20 25 30 35 40 40 6
total 16

La fusion de 15 40 et 25 40 compare 15 à 25, puis \(40_a\) à 25, puis \(40_a\) à \(40_b\) : à égalité, \(40_a\), de gauche, est copié d’abord, et la moitié gauche est épuisée ; \(40_b\) est copié sans comparaison. La fusion finale compare 6 fois : les deux 40 sont copiés à la fin sans comparaison, la moitié droite étant épuisée.

(c) \(\lceil\log_2 8!\rceil=\lceil15{,}30\rceil=16\). Le tri fusion fait 16 comparaisons, la borne elle-même ; le tri par insertion en fait 21, à cause des 16 inversions. Les deux tris gardent \(40_a\) devant \(40_b\) : ils sont stables, parce que leur comparaison stricte ne fait jamais passer un élément devant un élément égal.

Erreur fréquente : compter une comparaison quand une moitié est épuisée. Dans ce cas, la boucle de fusionner copie l’élément restant (lignes if (i > mid) et else if (j > hi)) sans appeler plusPetit.

À retenir

  • Une structure d’ensembles disjoints (union-find) maintient une partition de \(0,\dots,n-1\) : union, find, connected, count.
  • QuickFind range l’identifiant de chaque composante : find en un accès, union en \(\Theta(n)\). QuickUnion range une forêt : find coûte \(2d+1\) accès à la profondeur \(d\), et la hauteur peut atteindre \(n-1\).
  • L’union pondérée par la taille (ou par le rang) garde une hauteur au plus \(\log_2 n\) ; avec la compression de chemin, \(m\) opérations coûtent \(\mathcal{O}(m\,\alpha(n))\).
  • Kruskal avec union-find coûte \(\mathcal{O}(E\log E)\), le tas des arêtes ; le test de cycle ne coûte plus qu’une dizaine d’accès par arête.
  • Le tri par insertion fait un échange par inversion : \(n-1\) comparaisons sur un tableau trié, \(n(n-1)/2\) au pire, environ \(n^2/4\) en moyenne ; il est stable et en place.
  • Le tri fusion coûte \(\Theta(n\log n)\) dans tous les cas, avec \(n\) cases auxiliaires ; il est stable.
  • Le tri rapide (partition de Lomuto, pivot aléatoire) fait environ \(1{,}39\,n\log_2 n\) comparaisons en moyenne, \(n(n-1)/2\) au pire (certain avec des clés égales) ; il est en place et n’est pas stable.
  • Tout tri par comparaison fait au moins \(\lceil\log_2 n!\rceil=\Omega(n\log n)\) comparaisons au pire : l’arbre de décision a au moins \(n!\) feuilles.

Synthèse du cours

Les six séances ont construit des structures qui se choisissent par les opérations qu’elles rendent rapides. Les listes, piles, files et deques de la Séance 1, sur un tableau ou une liste chaînée, rangent des éléments dans un ordre d’arrivée ; la Séance 2 a donné les outils pour comparer les coûts (\(\mathcal{O}\), \(\Omega\), \(\Theta\), récurrences, théorème maître). La table de hachage de la Séance 3 accède à une clé en temps constant en moyenne, tant que son facteur de charge reste borné, mais ne garde aucun ordre ; les arbres équilibrés de la Séance 4 gardent l’ordre en \(\mathcal{O}(\log n)\) par opération, et le tas binaire donne le minimum en \(\mathcal{O}(\log n)\). Les graphes de la Séance 5 ont réuni ces structures : une file pour le parcours en largeur, la pile des appels pour le parcours en profondeur, le tas pour Dijkstra et Kruskal. Cette séance a complété Kruskal par union-find, puis montré que trier par comparaisons coûte \(\Theta(n\log n)\), ni plus avec le tri fusion, ni moins avec aucun tri.

séance structures et algorithmes coûts à retenir
1. Types abstraits listes, piles, files ; tableau ou liste chaînée ajout en fin \(\mathcal{O}(1)\) amorti
2. Analyse \(\mathcal{O}\), \(\Omega\), \(\Theta\), récurrences, théorème maître \(2T(n/2)+n=\Theta(n\log n)\)
3. Hachage chaînage, sondage linéaire, rehash \(\mathcal{O}(1)\) en moyenne, charge bornée
4. Arbres et tas ABR, AVL, tas binaire, tri par tas \(\mathcal{O}(\log n)\) (AVL, tas)
5. Graphes parcours, tri topologique, Dijkstra, Kruskal \(\Theta(V+E)\), \(\mathcal{O}((V+E)\log V)\)
6. Disjoints et tris union-find, insertion, fusion, rapide \(\mathcal{O}(\alpha(n))\), \(\Theta(n\log n)\)

Références

  • Sedgewick, Wayne — Algorithms, 4e éd., Addison-Wesley, 2011 (§ 1.5 : union-find ; § 2.1 : tris élémentaires ; § 2.2 : tri fusion et complexité du tri ; § 2.3 : tri rapide ; § 2.4 : tri par tas).
  • Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 2 : tri par insertion, tri fusion ; ch. 7 : tri rapide ; ch. 8 : borne inférieure, tri par dénombrement ; ch. 19 : structures de données pour ensembles disjoints).
  • Skiena — The Algorithm Design Manual, 3e éd., Springer, 2020 (ch. 4 : tri ; ch. 8 : union-find, avec les arbres couvrants minimaux).
  • Tarjan — « Efficiency of a good but not linear set union algorithm », Journal of the ACM, 22(2), 1975.
  • Hoare — « Quicksort », The Computer Journal, 5(1), 1962.

Pour cette séance

Les slides

À lire en ligne

À télécharger

Retour au sommet