% classe du document
\documentclass[12pt]{article}

% mise en page
\usepackage[paper=a4paper, portrait=true, twoside=false, left=1cm,
top=1cm, nohead, nomarginpar, includefoot, centering=true]{geometry}

% changer "utf8" en "latin1" selon la configuration
\usepackage{amssymb,amsmath}
%\usepackage[applemac]{inputenc}
\usepackage[francais]{babel}

%\usepackage[latin1]{inputenc} 
%\usepackage[frenchb]{babel}
%\frenchbsetup{og = «, fg = »}
\DecimalMathComma

% fontes latin modern
\usepackage[T1]{fontenc}
\usepackage{lmodern}

\usepackage[french,boxruled,inoutnumbered]{algorithm2e}

% pas d'ent�te
% num\' ero de page centr\' e en pied de page
\usepackage{fancyhdr} \pagestyle{fancy} \fancyhead{} \fancyfoot{}
\lfoot{} \cfoot{\thepage} \rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0.4pt}

% inclusion de graphiques
\usepackage{graphicx}

\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Cadre de pr\' esentation %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pas d'alin\' ea en d\' ebut de paragraphe
\setlength{\parindent}{0mm}
% \`a gauche : logo AMECI 
\begin{minipage}{2.5cm}
  \begin{flushleft}
    \includegraphics[width=2.5cm]{amecmi}
  \end{flushleft}
\end{minipage}
% au centre : titre de l'activit\' e
\begin{minipage}{14cm}
  \begin{center}
    {\bf \Huge Algorithmique : le tri \` a bulles} 

    Fiche \' el\`eve
  \end{center}
\end{minipage}
% \`a droite : niveau
\begin{minipage}{2.5cm}
  \begin{flushright}
    {\Huge 2\ieme}
  \end{flushright}
\end{minipage}
% en-dessous, \`a droite : nom de l'auteur
\begin{flushright}
  Auteur : Jean-Marc Duquesnoy et Raymond Moch\' e
\end{flushright}

{\bf 1 -} Apparemment, on peut ranger deux nombres donn\' es $a$ et $b$ \` a l'aide de l'algorithme suivant :\\
\begin{algorithm}[H]
\SetLine
\Entree{

nombres $a$ et $b$ \; }
\Sortie{

minimum puis maximum des nombres $a$ et $b$ \;}
\Deb{
\Si {$a>b$}{
$a\;\leftarrow\;b$ \;
$b\;\leftarrow\;a$ \;
}
Afficher $a,\,b$}
\caption{\' Ecrire 2 nombres $a$ et $b$ dans l'ordre croissant}
\end{algorithm}
$a\;\leftarrow\;b$ signifie que le contenu de la case $b$, qui est le nombre $b$, vient se mettre \` a la place du contenu de la case $a$ (qui \' etait le nombre $a$). En sortie, on demande d'afficher successivement les contenus des cases $a$ et $b$.\\
\textbf{Question -} Pourquoi cet algorithme est-il incorrect ? Quel r\' esultat donne-t-il ?\vspace{1mm}\\
{\bf 2 -} Voici un algorithme correct pour ordonner $a$ et $b$ dans l'ordre croissant :\\
\begin{algorithm}[H]
\SetLine
\Entree{

nombres $a$ et $b$ \;}
\Sortie{

minimum puis maximum des nombres $a$ et $b$ \;}
\Deb{
\Si {$a>b$}{
\' echanger a et b \;}
Afficher $a,\,b$}
\caption{\' Ecrire 2 nombres $a$ et $b$ dans l'ordre croissant}
\end{algorithm}
On voit que le probl\`eme est d'\' echanger le contenu des 2 cellules $a$ et $b$. \\
\textbf{Question -} Donner une solution utilisant une cellule auxiliaire $c$. La r\' eponse sera donn\' ee en compl\' etant le cadre vide de l'algorithme ci-dessous : \\
\begin{algorithm}[H]
\SetLine
\Entree{

nombres $a$ et $b$ \;}
\Sortie{

minimum puis maximum des nombres $a$ et $b$ \;}
\Deb{
\Si {$a>b$}{
\fbox{
\begin{minipage}{1.5cm}
\ \\
\ \\
\ \\
\end{minipage}
}
}
Afficher $a,\,b$
}
\caption{\' Ecrire 2 nombres $a$ et $b$ dans l'ordre croissant}
\end{algorithm}
{\bf 3 - Qu'est-ce que le \og tri \` a bulles\fg\, ?}\vspace{1mm}\\
Supposons que l'on ait \` a ordonner dans l'ordre croissant la suite\vspace{1mm}\\
\centerline{ $A=5,\,1,\,4,\,8,\,2$.}\vspace{1mm}\\
 La \textsl{manipulation de base} du \og tri \` a bulles\fg consiste \` a examiner \textsl{successivement} les couples form\' es par les nombres de rang 1 et 2, puis par les nombres de rang 2 et 3 et ainsi de suite jusqu'\` a la fin et de leur appliquer le traitement suivant :\vspace{1mm}\\
\centerline{\fbox{
\begin{minipage}{8cm}
On laisse inchang\' e tout couple qui est d\' ej\` a rang\' e dans l'ordre croissant ; dans le cas contraire, on \' echange ses 2 termes.
\end{minipage}
}}\vspace{1mm}\\
Voici les transformations successives subies par $A$ au cours de ce processus :\vspace{2mm}\\
\centerline{
$A=\underbar{5,\,1},\,4,\,8,\,2\;\rightarrow\; 1,\,\underbar{5,\,4},\,8,\,2\;\rightarrow\; 1,\,4,\,\underbar{5,\,8},\,2\;\rightarrow\; 1,\,4,\,5,\,\underbar{8,\,2}\;\rightarrow\; B=1,\,4,\,5,\,2,\,8$ }\vspace{2mm}\\
La suite $B$ n'est pas ordonn\' ee dans l'ordre croissant mais \textsl{nous avons fait des progr\` es} dans le classement car le maximum de $5,\,1,\,4,\,8,\,2$, qui est 8, se trouve maintenant \` a la fin de la suite, qui est sa place d\' efinitive.\vspace{1mm}\\
Cela conduit naturellement \` a appliquer \` a $B$ la \textsl{manipulation de base}. Voici ce que cela donne \vspace{2mm}\\
\centerline{
$B=\underbar{1,\,4},\,5,\,2,\,8\;\rightarrow\; 1,\,\underbar{4,\,5},\,2,\,8\;\rightarrow\; 1,\,4,\,\underbar{5,\,2},\,8\;\rightarrow\; 1,\,4,\,2,\,\underbar{5,\,8}\;\rightarrow\; C=1,\,4,\,2,\,5,\,8$ }\vspace{2mm}\\
C'est mieux car les 2 derniers termes sont maintenant \` a leurs places d\' efinitives. Recommen\c{c}ons en appliquant la manipulation de base \` a $C$ :\vspace{2mm}\\
\centerline{
$C=\underbar{1,\,4},\,2,\,5,\,8\;\rightarrow\; 1,\,\underbar{4,\,2},\,5,\,8\;\rightarrow\; 1,\,2,\,\underbar{4,\,5},\,8\;\rightarrow\; 1,\,2,\,4,\,\underbar{5,\,8}\;\rightarrow\; 1,\,2,\,4,\,5,\,8$ }\vspace{2mm}\\
On voit que le rangement de $A$ dans l'ordre croissant est termin\' e. Pour cela, on a d\^ u appliquer 3 fois la manipulation de base.\vspace{1mm}\\
Si on imagine maintenant que $A$ est une suite quelconque  de $n\ge2$ nombres quelconques, il est clair qu'apr\` es une premi\` ere application de la \textsl{manipulation de base}, le dernier terme du nouvel \' etat de $A$ sera \` a sa place d\' efinitive ; apr\` es la seconde application de la \textsl{manipulation de base}, les 2 derniers termes seront \` a leurs places d\' efinitives, et ainsi de suite. Par cons\' equent, apr\` es la $(n-1)$\up{\`eme} application de la \textsl{manipulation de base}, les $(n-1)$ derniers termes - et par cons\' equent le premier - seront \` a leurs places d\' efinitives, ce qui veut dire que le rangement sera termin\' e. L'exemple $A=5,\,1,\,4,\,8,\,2$ montre que, quelquefois, il n'y a pas besoin d'effectuer les $(n-1)$ applications de la \textsl{manipulation de base}.\vspace{1mm}\\
\textbf{Question -}  Combien faut-il de \textsl{manipulations de base} pour ranger $5,\, 4,\,3,\,2,\,1$ dans l'ordre croissant ?\vspace{1mm}\\
\centerline{\fbox{
\begin{minipage}{11cm}
Nous retiendrons que nous sommes s\^ urs que $A$ est rang\' e dans l'ordre croissant au bout de $(n-1)$ \textsl{manipulations de base}.
\end{minipage}
}} \vspace{2mm}\\
{\bf 4 -} Voici l'algorithme du \og tri \` a bulles\fg, en langage naturel :\\
\begin{algorithm}[H]
\SetLine
\Entree{

$A=a_1,\,\ldots,\,a_n$, suite d'au moins 2 nombres \;}
\Sortie{

la suite obtenue en rangeant $A$ dans l'ordre croissant \;}
\Deb{
$n\;\leftarrow\;$ longueur de la suite $A$ \;
\Pour {$k=1,\,\ldots,\,(n-1)$}{
\Pour{$j=1,\,\ldots,\,(n-1)$}{

\Si {$a_j>a_{j+1}\vspace{1mm}$}{
$c\;\leftarrow\;a_j$ \;
$a_j\;\leftarrow\;a_{j+1}$ \;
$a_{j+1}\;\leftarrow\;c$
}}}
Afficher $A$
}
\caption{Algorithme du tri \` a bulles}
\end{algorithm}
\textbf{Question -} Modifier cet algorithme pour que l'\' etat initial de la suite $A$ soit conserv\' e et affich\' e en m\^eme temps que le r\' esultat.\vspace{2mm}\\
{\bf 5 -} Ouvrir le fichier \og TriBulles.sci\fg qui contient l'algorithme du \og tri \` a bulles\fg sous une forme ex\' ecutable par \og scilab pour les lyc\' ees\fg ou le fichier \og TriBullesXcas.xws\fg ex\' ecutable par \og Xcas\fg.\vspace{1mm}\\
{\bf 5.a -} \`A l'aide de cet algorithme, ranger $A=5,\,1,\,4,\,8,\,2$ dans l'ordre croissant.\vspace{1mm}\\
{\bf 5.b -} Tirer 300 entiers au hasard entre 213 et 945 ; les ranger dans l'ordre croissant.\vspace{1mm}\\
On remarquera que ce calcul est long.\vspace{1mm}\\
{\bf 5.c -} Recommencer le tri en utilisant la fonction pr\' e-programm\' ee\og trier \fg (\og sort\fg) de \og scilab pour les lyc\' ees\fg ou \og SortD\fg de \og Xcas\fg. Que constate-t-on ?\vspace{1mm}\\
\textsl{Remarque} Les fonctions \og trier \fg et \og SortD\fg trient dans l'ordre d\' ecroissant.\vspace{1mm}\\
{\bf 5.d - }Tirer au hasard 100000 nombres quelconques entre 0 et 1. Ranger ces nombres dans l'ordre croissant.\vspace{1mm}\\
\textsl{Commentaires} Ce tri aurait \' et\' e impossible (essayer) avec l'algorithme du \og tri \` a bulles\fg tel que nous l'avons \' ecrit. L'algorithme du \og tri \`a bulles\fg, m\^eme optimis\' e, n'est pas tr\`es bon. Les sp\' ecialistes font beaucoup mieux.





















\end{document}