Solutions
450
Solu tionS deS exer ciceS du cha pitre 2
2.1 1) On effec tue n 2 1 com pa rai sons lors de la 1
ère
phase, n 2 2 com pa rai sons lors de la
2
ème
, ..., 1 com pa rai son lors de la (n 2 1)
ème
phase.
La com plexité est : (n 2 1) 1 (n 2 2) 1 c , 1 1 5 n(n 2 1)/2, soit en O(n
2
).
Le lec teur trou vera dans l’exer cice sui vant un tri de com plexité moindre, en O(n log n).
Sup po sons que l’on doive trier n = 1 000 élé ments : par un tri par trans po si tions on effec tuera
plus de 500 000 com pa rai sons et seule ment de l’ordre de 10 000 com pa rai sons pour un tri en
O(n log n) (nous approximons ici log 1 000 par log 1 024, c’estàdire log 2
10
= 10).
2) Les n cases du tableau sont notées : Tab(1), Tab(2), ..., Tab(n).
pour i 5 1 à n 2 1
pour j 5 1 à n 2 i
si Tab( j) . Tab( j 1 1) alors
élt d Tab( j 1 1) ; Tab( j 1 1) d Tab( j) ; Tab( j) d élt ;
fin si
fin pour
fin pour
2.2 1) Le nombre d’élé ments du tableau étant 9, l’algo rithme com mence par trier d’une part
le tableau 7 5 2 8 et le tableau 4 1 3 9 6 avant de fusion ner ces deux tableaux en
uti li sant l’algo rithme pré senté à la ques tion pré cé dente.
Appli quons l’algo rithme de tri au tableau de gauche : 7 5 2 8 . Ce tableau com por tant
plus de deux élé ments, l’algo rithme doit être exé cuté pour les tableaux 7 5 et 2 8 avant
qu’ils soient fusion nés. L’algo rithme appli qué à 7 5 com mence par sépa rer ce tableau en
deux tableaux 7 et 5 . Ces deux tableaux étant de taille uni taire, ils consti tuent cha cun un
tableau trié ; le résul tat de leur fusion est alors 5 7 . De même, l’appli ca tion de l’algo rithme
de tri au tableau 2 8 don nera 2 8 et la fusion des deux tableaux 5 7 et 2 8 aura
pour résul tat 2 5 7 8 .
Le tableau 4 1 3 9 6 est d’abord scindé en deux tableaux : 4 1 et 3 9 6 . Pour
le tableau 4 1 , après une nou velle sépa ra tion et une fusion, le tableau résul tat est 1 4 . Le
tableau 3 9 6 est lui séparé en 3 et 9 6 . L’algo rithme de tri est appli qué à ce der nier
tableau de deux élé ments et le tableau résul tant est 6 9 ; sa fusion avec 3 donne 3 9 6 ,
qui lui même fusionné avec 1 4 four nit le tableau 1 3 4 6 9 .
Fina le ment, la fusion des deux tableaux 2 5 7 8 et 1 3 4 6 9 donne comme
résul tat 1 2 3 4 5 6 7 8 9 .
2) Mon trons qu’après k pas sages dans la boucle de l’ins truc tion 2, les k pre miers élé ments
du tableau Τ ont été cor rec te ment insé rés. Notons pre mière ment qu’à cha cun des pas sages
un et un seul élé ment est inséré dans le tableau. Soit a le der nier élé ment inséré et sup po sons
qu’à cette étape T1(i 1 ) < T 2(i 2 ) (le rai son ne ment est évi dem ment iden tique dans le cas
450
Solu tionS deS exer ciceS du cha pitre 2
2.1 1) On effec tue n 2 1 com pa rai sons lors de la 1
ère
phase, n 2 2 com pa rai sons lors de la
2
ème
, ..., 1 com pa rai son lors de la (n 2 1)
ème
phase.
La com plexité est : (n 2 1) 1 (n 2 2) 1 c , 1 1 5 n(n 2 1)/2, soit en O(n
2
).
Le lec teur trou vera dans l’exer cice sui vant un tri de com plexité moindre, en O(n log n).
Sup po sons que l’on doive trier n = 1 000 élé ments : par un tri par trans po si tions on effec tuera
plus de 500 000 com pa rai sons et seule ment de l’ordre de 10 000 com pa rai sons pour un tri en
O(n log n) (nous approximons ici log 1 000 par log 1 024, c’estàdire log 2
10
= 10).
2) Les n cases du tableau sont notées : Tab(1), Tab(2), ..., Tab(n).
pour i 5 1 à n 2 1
pour j 5 1 à n 2 i
si Tab( j) . Tab( j 1 1) alors
élt d Tab( j 1 1) ; Tab( j 1 1) d Tab( j) ; Tab( j) d élt ;
fin si
fin pour
fin pour
2.2 1) Le nombre d’élé ments du tableau étant 9, l’algo rithme com mence par trier d’une part
le tableau 7 5 2 8 et le tableau 4 1 3 9 6 avant de fusion ner ces deux tableaux en
uti li sant l’algo rithme pré senté à la ques tion pré cé dente.
Appli quons l’algo rithme de tri au tableau de gauche : 7 5 2 8 . Ce tableau com por tant
plus de deux élé ments, l’algo rithme doit être exé cuté pour les tableaux 7 5 et 2 8 avant
qu’ils soient fusion nés. L’algo rithme appli qué à 7 5 com mence par sépa rer ce tableau en
deux tableaux 7 et 5 . Ces deux tableaux étant de taille uni taire, ils consti tuent cha cun un
tableau trié ; le résul tat de leur fusion est alors 5 7 . De même, l’appli ca tion de l’algo rithme
de tri au tableau 2 8 don nera 2 8 et la fusion des deux tableaux 5 7 et 2 8 aura
pour résul tat 2 5 7 8 .
Le tableau 4 1 3 9 6 est d’abord scindé en deux tableaux : 4 1 et 3 9 6 . Pour
le tableau 4 1 , après une nou velle sépa ra tion et une fusion, le tableau résul tat est 1 4 . Le
tableau 3 9 6 est lui séparé en 3 et 9 6 . L’algo rithme de tri est appli qué à ce der nier
tableau de deux élé ments et le tableau résul tant est 6 9 ; sa fusion avec 3 donne 3 9 6 ,
qui lui même fusionné avec 1 4 four nit le tableau 1 3 4 6 9 .
Fina le ment, la fusion des deux tableaux 2 5 7 8 et 1 3 4 6 9 donne comme
résul tat 1 2 3 4 5 6 7 8 9 .
2) Mon trons qu’après k pas sages dans la boucle de l’ins truc tion 2, les k pre miers élé ments
du tableau Τ ont été cor rec te ment insé rés. Notons pre mière ment qu’à cha cun des pas sages
un et un seul élé ment est inséré dans le tableau. Soit a le der nier élé ment inséré et sup po sons
qu’à cette étape T1(i 1 ) < T 2(i 2 ) (le rai son ne ment est évi dem ment iden tique dans le cas