Fusion naturelle

Le sous-tableau $T [d : f]$ est déjà trié : on ne trie que les deux autres morceaux, puis on fait deux fusions.


static void triNaturel(int[] T, int i, int j, int[] B) { // trie T[i:j]
    if (j - i <= 1) return;
    int[] df = pplstc(T, i, j); int d = df[0], f = df[1];
    triNaturel(T, i, d, B);           // T[i:d] trié
    triNaturel(T, f, j, B);           // T[f:j] trié ; T[d:f] l'était déjà
    fusionner(T, i, d, f, B);         // T[i:f] trié
    fusionner(T, i, f, j, B);         // T[i:j] trié
}


nom : T
valeurs : 3 2 1 1 2 4 1 2 2 4
vert : 2..5
pointeurs : d=2 f=6
zone : 0..1 récursif
zone : 2..5 déjà trié
zone : 6..9 récursif
legende : sur l'exemple du pplstc : seuls T[0:2] et T[6:10] sont triés par appel

La fonction pplstc(T, i, j) est celle de l'exercice 12.8, appliquée à $T [i : j]$ ; fusionner est celle du cours. Mesures pour $n = 1 0^{6}$ (programme Mesures.java) :


14.4 presque trie n=1000000 : fusion 26,9 ms, naturelle 9,4 ms, egaux=true
14.4 aleatoire    n=1000000 : fusion 115,5 ms, naturelle 201,9 ms, egaux=true

Sur le tableau presque trié, le premier plus long sous-tableau croissant couvre une grande partie du tableau : le tri naturel est environ trois fois plus rapide. Sur un tableau aléatoire, ce sous-tableau est très court (de l'ordre de quelques cases), le découpage est déséquilibré et le tri naturel est presque deux fois plus lent. Une bonne méthode pour les données presque triées n'est pas forcément bonne pour toutes : le tri de Java pour les objets (Timsort) détecte ces séquences croissantes sans perdre en temps sur les données aléatoires.

Énoncé

Corrigé