Tri par dénombrement stable — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 14)

Tri par dénombrement stable

Les tris · niveau 2

Énoncé

On veut trier des couples (note, numéro d'étudiant), les notes étant des entiers de $[0 : 21]$ , selon la note et de façon stable : deux étudiants de même note restent dans l'ordre de départ. Modifier le tri par dénombrement pour cela, en calculant pour chaque note $x$ la case où commence la zone des notes $x$ dans le tableau trié. Trier $(12, 101), (8, 102), (12, 103), (15, 104), (8, 105), (12, 106)$ .

Corrigé

On compte d'abord les couples de chaque note, puis on calcule $debut [x] = nb [0] + \dots + nb [x - 1]$ : c'est la première case de la zone des notes $x$ dans le tableau trié. On parcourt enfin les couples de gauche à droite et on range chacun dans la prochaine case libre de sa zone : deux couples de même note gardent leur ordre de départ.


static int[][] triStable(int[][] C, int v) { int n = C.length; // notes dans [0:v]
    int[] nb = new int[v];
    for (int[] c : C) nb[c[0]]++;          // nb[x] : nombre de couples de note x
    int[] debut = new int[v];
    // I(x) : debut[x] = nb[0] + ... + nb[x-1]
    for (int x = 1; x < v; x++) debut[x] = debut[x - 1] + nb[x - 1];
    int[][] R = new int[n][];
    for (int[] c : C) R[debut[c[0]]++] = c; // gauche à droite : stable
    return R;
}


14.8 : (8,102) (8,105) (12,101) (12,103) (12,106) (15,104)


nom : R
valeurs : 102 105 101 103 106 104
zone : 0..1 note 8
zone : 2..4 note 12
zone : 5..5 note 15
legende : numéros rangés : debut[8] = 0, debut[12] = 2, debut[15] = 5

Les étudiants $101$ , $103$ , $106$ (note $12$ ) restent dans cet ordre. La complexité est $Θ (n + v)$ . C'est cette version stable qui sert de brique au tri par base (tri des entiers chiffre par chiffre).