- Tri a bulles `
On considere l'algorithme de tri ` a bulles suivant : `
def Push(tab,k)
j=1
while j<k:
           if tab[j]<tab[j-1]:
                  tmp=tab[j-1]
                  tab[j-1]=tab[j]
                  tab[j]=tmp
           j=j+1


def BubleSort(tab):
i=0
n=len(tab)
while i<n :
             Push(tab, n-i)
             i=i+1
            print("i=", i, " tab=", tab)


Question 3
On commence par etudier la validit ´ e de ´ Push.
Soit tab1 = tab et pour j ∈ {2, · · · , k}, tabj designe le tableau ´ tab obtenue a la fin du corps de boucle de ` Push
(apres l'incr ` ementation de ´ j).
Soit alors la propriet´ e´ Π(j), j ∈ {1, · · · , k} :
— tabj [j · · · n − 1] = tab1[j · · · n − 1]
— tabj [0 · · · j − 1] est constitue des ´ el´ ements de ´ tab1[0 · · · j − 1] de sorte que tabj [j − 1] contienne le plus grand
el´ ement de ce sous-tableau. ´
Montrez la propriet´ e´ Π(j), j ∈ {1, · · · , k} par recurrence sur ´ j.