Dans le répertoire Python créez un dossier cours6. Il contiendra tous les fichiers de cette leçon.

Trois méthodes de tri

Tri par sélection

Écrire un programme tri_selection.py permettant de trier un tableau, c’est-à-dire ordonner les valeurs des éléments dans l’ordre croissant. On utilisera la méthode suivante:

Un seul tableau est utilisé lors de ce tri. On supposera le tableau déjà initialisé.
Exemple :

Aide : Algorithme

Tri à bulle

Cette méthode consiste à faire remonter progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la surface d'un liquide. On compare deux élément successifs et on les permute éventuellement. Le tri est fini lorsque sur un passage aucune permutation a été réalisée. Pour cela on pourra utiliser une variable booléenne tri qui prend la valeur false dès que l'on fait une permutation.
Exemple :

1er passage	2ième passage	3ième passage	4ième passage
[30,10,1,5,20,7,7] [10,30,1,5,20,7,7] [10,1,30,5,20,7,7] [10,1,5,30,20,7,7] [10,1,5,20,30,7,7] [10,1,5,20,7,30,7] [10,1,5,20,7,7,30]	[10,1,5,20,7,7,30] [1,10,5,20,7,7,30] [1,5,10,20,7,7,30] [1,5,10,7,20,7,30] [1,5,10,7,7,20,30]	[1,5,10,7,7,20,30] [1,5,7,10,7,20,30] [1,5,7,7,10,20,30]	[1,5,7,7,10,20,30]

Écrire un programme tri_bulle.py qui applique cette méthode

Aide : Algorithme

Le tri par insertion

Principe

Le tableau comporte une partie triée et une autre non triée.
On insère dans la partie triée, au bon endroit, le premier élément de la partie non triée de façon à obtenir une partie triée augmentée d'un élément.
On a fini lorsque la partie non triée est vide.

Exemple :

Soit le tableau T=[3, 10, 1, 8, 52, 22].

Aide : Algorithme

Recherche d'un élément dans une liste triée

Recherche simple

Écrire un programme recherche.py permettant de retrouver une valeur dans une liste triée, cette valeur sera saisie au clavier.
On indiquera en résultat, la position de la valeur dans la liste. La valeur recherchée peut aussi être absente de la liste.

Aide : Algorithme

Recherche par dichotomie.

Exemples : L=[1,5,7,7,20,30]

1. On cherche 5 $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2 &&&\\ &~~& T[2]=7 &&&\\ & & 5 < 7 &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline inf=0 & sup=milieu-1=1&&&\\ ~milieu=\dfrac{0+1}{2}=0& & &&&\\ T[0]=1 &&&&&\\ 5>1 && &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & inf=milieu+1=1 &&&\\ & sup=1&&&\\ &~milieu=\dfrac{1+1}{2}=1 & &&&\\ &T[1]=5 &&&&\\ \hline \end{array}$$
2. On cherche 30. $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2& &&\\ && T[2]=7& &&\\ & & 30>7 & &&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & &&inf=milieu+1=3 &milieu=\dfrac{3+5}{2}=4&sup=5\\ & & &&&\\ & &&&T[4]=20&\\ & & &&30>20&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & &&& &inf=milieu+1=5\\ & & &&&~milieu=\dfrac{5+5}{2}=5\\ &&&&&T[5]=30 \\ \hline \end{array}$$
3. On cherche 2 $$\begin{array}{|c|c|c|c|c|c|}\hline 1&5&7&7&20&30\\ \hline inf=0&&&&&sup=5\\ && milieu=\dfrac{0+5}{2}=2 &&&\\ &~~& T[2]=7 &&&\\ & & 2 < 7 &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline inf=0 & sup=milieu-1=1&&&\\ ~milieu=\dfrac{0+1}{2}=0& & &&&\\ T[0]=1 &&&&&\\ 2>1 && &&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline & inf=milieu+1=1 &&&\\ &~milieu=\dfrac{1+1}{2}=1 & &&&\\ &T[1]=5 &&&&\\ &2<5 &&&&\\ \hline ~~~~~~~~~~~~1~~~~~~~~~~~~&~~~~~~~~~~~~5~~~~~~~~~~~~& ~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~7~~~~~~~~~~~~&~~~~~~~~~~~~20~~~~~~~~~~~~&~~~~~~~~~~~~30~~~~~~~~\\ \hline sup=milieu-1=0&inf&&&&\\ \hline \end{array}$$

• On prend les k premières valeurs de points, $voisins=[x_0,\,x_1,\, ......x_{k-1}]$
• On note y la valeur de voisins la plus éloignée de x
• Pour chacune des valeurs restantes de points c'est à dire de la sous liste $[x_{k},\,x_{k+1},\, ............... x_{n-1}]$
on regarde si elle est plus proche de $x$ que $y$.
Si c'est le cas on remplace $y$ par cette valeur dans voisins.

• voisins =[22,30,20].
  30 est la valeur la plus éloignée de 10.
  On compare compare 30 avec 8, la première valeur de la sous liste [8,5,50,7].
  8 est plus proche que 30 on obtient voisins =[22,8,20]
• voisins =[22,8,20].
  22 est la valeur la plus éloignée de 10.
  On compare 22 avec 5, la deuxième valeur de la sous liste [8,5,50,7].
  5 est plus proche que 22 on obtient voisins =[5,8,20]
• voisins =[5,8,20].
  20 est la valeur la plus éloignée de 10.
  On compare 20 avec 50, la troisième valeur de la sous liste [8,5,50,7].
  20 est plus proche que 50 on conserve voisins =[5,8,20]
• voisins =[5,8,20].
  20 est la valeur la plus éloignée de 10.
  On compare 20 avec 7, la quatrième valeur de la sous liste [8,5,50,7].
  7 est plus proche que 20 on obtient voisins =[5,8,7]