\input{../.headers/synthèse.tex}

\baselineskip15pt

\begin{center}
\shadowbox{\LARGE \bf \textsc{\supline Listes/tableaux/tris~: r\'esum\'e
\subline}}\\
\end{center}

\section{Listes (cha\^in\'ees) vs Tableaux}

\subsection{Sp\'ecificit\'es}
\ \\[-0.75cm]

\fbox{\begin{minipage}{6.5cm}
~~~~~~~~~~~~~~Listes~:
\begin{enumerate}
\item[\smiley] Insertion possible d'un \'el\'ement.
\item[\frownie] Acc\`es au $k^e$ \'el\'ement en $O(k)$.
\end{enumerate}
\end{minipage}}
~~~~~~~~~~~~~~
\fbox{\begin{minipage}{7.5cm}
~~~~~~~~~~~~~~~~~~~~Tableaux~:
\begin{enumerate}
\item[\frownie] Modification de la longueur impossible.
\item[\smiley] Acc\`es au $k^e$ \'el\'ement en $O(1)$.
\end{enumerate}
\end{minipage}}

\subsection{Remarque}

Python utilise des tableaux redimensionnables. C'est mieux, mais hors-programme.\subline

\subsection{Un principe g\'en\'eral}

Pour l'impl\'ementation des algorithmes (en g\'en\'eral, en particulier les tris mais pas que=~:\megasubline
\begin{enumerate}
\item De par leurs sp\'ecificit\'es, les tableaux sont naturellement adapt\'es \`a des traitements \megasubline
\item De par leurs sp\'ecificit\'es, les listes sont naturellement adapt\'ees \`a des traitements \\
\end{enumerate}


\section{Algorithmes de tri}

\subsection{Remarques}

Remarque~:\begin{itemize}[$\bullet$]
\item Les listes sont des structures de donn\'ees immuables (on dit aussi~: persistantes). Pour trier une liste, on {\bf retourne une nouvelle liste} ayant les m\^emes \'el\'ements mais tri\'ee.
\item Les tableaux sont des structures de donn\'ees modifiables (on dit aussi~: imp\'eratives). Pour trier un tableau, on ne retourne rien, mais on {\bf modifie le tableau de d\'epart} pour qu'il soit tri\'e.
\end{itemize}

Remarque~: un tri sur un tableau est dit "en place" lorsqu'il ne n\'ecessite pas la cr\'eation d'un tableau auxilliaire.


\subsection{Tri par s\'election}
Le tri par s\'election consiste, pour trier une liste (ou un tableau) \`a~:
\begin{enumerate}[$\bullet$]
\item D\'eterminer l'\'el\'ement minimal de la liste ou du tableau~;
\item Le permuter pour le passer en t\^ete.
\item Recommencer sur les \'el\'ements restants.
\end{enumerate}
Variante~: on prend l'\'el\'ement maximal.\\
Complexit\'e dans le pire des cas~: $\Theta(n^2)$

\subsection{Tri par insertion}
Le tri par insertion consiste, pour trier une liste (ou un tableau) \`a parcourir les \'el\'ements liste (/ le tableau) en ins\'erant successivement chaque \'el\'ement \`a sa place dans la liste d\'ej\`a tri\'ee des \'el\'ements pr\'ec\'edents (initialement vide).\\
Variante~: on ins\`ere r\'ecursivement dans la liste d\'ej\`a tri\'ee des \'el\'ements suivants.\\
Complexit\'e dans le pire des cas~: $\Theta(n^2)$

\subsection{Tri par fusion}
Le tri par fusion consiste, pour trier une liste (ou un tableau) \`a~:
\begin{enumerate}[$\bullet$]
\item Diviser la liste (/ le tableau) en deux moiti\'es~;
\item Trier r\'ecursivement chacune des deux moiti\'es~;
\item Fusionner les deux moiti\'es tri\'ees pour reconstituer la liste (/ le tableau) tri\'ee.
\end{enumerate}
Complexit\'e dans le pire des cas~: $\Theta(n \lg n)$

\subsection{Tri rapide (tri par pivot)}
Le tri par pivot consiste, pour trier une liste (ou un tableau) \`a~:
\begin{enumerate}[$\bullet$]
\item Prendre le premier \'el\'ement du tableau ou de la liste \`a trier~; on l'appelle le pivot~;
\item Diviser le reste de la liste (/ du tableau) en deux moiti\'es~: les \'el\'ements plus petits que le pivot, et les \'el\'ements plus grands~;
\item Trier r\'ecursivement chacune des deux moiti\'es~;
\item Raccorder les trois morceaux dans l'ordre.
\end{enumerate}
Complexit\'e dans le pire des cas~: $\Theta(n \lg n)$\\
Complexit\'e en moyenne~: 


\subsection{Tri \`a bulles}
Le tri \`a bulles consiste, pour trier une liste (ou un tableau) \`a~:
\begin{enumerate}[$\bullet$]
\item Parcourir la liste (/ le tableau) en permutant deux \'el\'ements cons\'ecutif \`a chaque fois qu'ils ne sont pas dans le bon ordre~;
\item Recommencer sur les n-1 premiers \'el\'ements de la liste (/ du tableau)~; etc.
\end{enumerate}
Complexit\'e dans le pire des cas~: $\Theta(n^2)$

\end{document}
