À partir du livre clrs, pourquoi le tri d'insertion de la boucle est-il répété n fois?

Question

Pourquoi la première ligne est-elle répétée n fois, quand elle commence à 2? Ne devrait-il pas être n-1 à la place? Aussi pourquoi est-ce que les lignes 2 et 3 sont n-1 et non n?

Answer 1

Ici, l'instruction de boucle est considérée comme étant exécutée une fois de plus, car elle est comparée avant la première itération et après la dernière itération. Considérons A.length = 3. Nous avons seulement deux itérations, mais trois comparaisons:

j := 2 
if j > A.length then exit the loop // first comparison, false 
... first loop iteration goes 

j := j + 1 // j = 3 now 
if j > A.length then exit the loop // second comparison, false 
... second loop iteration goes 

j := j + 1 // j = 4 now 
if j > A.length then exit the loop // third comparison, true 

Ainsi, comme vous pouvez le voir, nous devons comparer trois fois, mais le corps de la boucle est exécutée deux fois seulement. La première comparaison est nécessaire, car si A.length = 1 nous ne devrions pas exécuter le corps de la boucle du tout.