diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/Makefile.am | 11 | ||||
| -rw-r--r-- | doc/README.en | 0 | ||||
| -rw-r--r-- | doc/README.fr | 0 | ||||
| -rw-r--r-- | doc/algo.tex | 89 | ||||
| -rw-r--r-- | doc/algorithmes.tex | 57 | ||||
| -rw-r--r-- | doc/bib.tex | 7 | ||||
| -rw-r--r-- | doc/conclusion.tex | 9 | ||||
| -rw-r--r-- | doc/description.tex | 19 | ||||
| -rw-r--r-- | doc/intro.tex | 11 | ||||
| -rw-r--r-- | doc/manuel.tex | 124 | ||||
| -rw-r--r-- | doc/outils.tex | 21 | ||||
| -rw-r--r-- | doc/structures.tex | 64 | ||||
| -rw-r--r-- | doc/temps.tex | 26 |
13 files changed, 437 insertions, 1 deletions
diff --git a/doc/Makefile.am b/doc/Makefile.am index ee5aba4..d27abf6 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -1 +1,10 @@ -EXTRA_DIST = README.fr README.en +ps: + make -f Makefile.doc ps + +clean: + make -f Makefile.doc clean + +distclean: + make -f Makefile.doc clean + +EXTRA_DIST = algo.tex algorithmes.tex bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex structures.tex temps.tex diff --git a/doc/README.en b/doc/README.en deleted file mode 100644 index e69de29..0000000 --- a/doc/README.en +++ /dev/null diff --git a/doc/README.fr b/doc/README.fr deleted file mode 100644 index e69de29..0000000 --- a/doc/README.fr +++ /dev/null diff --git a/doc/algo.tex b/doc/algo.tex new file mode 100644 index 0000000..c1c164e --- /dev/null +++ b/doc/algo.tex @@ -0,0 +1,89 @@ +%initialisations---------------------------------------------------------------- +\documentclass[french,11pt,a4paper,twoside,openright]{report} +\usepackage[T1]{fontenc} +\usepackage[latin1]{inputenc} +\usepackage[francais]{babel} +\usepackage{a4} +\usepackage{ulem} +\usepackage{multirow} +\usepackage[dvips]{graphics} +\usepackage{vmargin} +\usepackage{fancyhdr} +\usepackage{oldstyle} +\usepackage{listings} +\usepackage{verbatim} +%fin des initialisations-------------------------------------------------------- + +\pagestyle{fancyplain} +\addtolength{\headwidth}{\marginparsep} +\addtolength{\headwidth}{\marginparwidth} +% titre de chapitre +\renewcommand{\chaptermark}[1]{\markboth{#1} {}} +% titre de section +\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}} + +\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}} +\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}} +\cfoot{\fancyplain{\textos{\thepage}}{}} + +\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}} + +\def\addcontentsline#1#2#3{% + \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}} +% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin} +\setmargrb{1.5cm}{2cm}{1.5cm}{4cm} + +\begin{document} +\renewcommand{\chaptername}{Section} +\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$} + +%page de garde +\title{Projet d'Algorithmique\\ + Rapport \vspace{1.0cm}} +\author{Barrère Jordi, Noble Nicolas\vspace{2.0cm}} +\date{\textit{dernière révision: \today}} +\maketitle +\strut\thispagestyle{empty} +\vfill +\pagebreak +\setcounter{page}{1} + + + +\tableofcontents + +\clearemptydoublepage + +\input{intro} +\clearemptydoublepage +\part{Analyse} +\input{description} +\clearemptydoublepage +\input{structures} +\clearemptydoublepage +\input{algorithmes} +\clearemptydoublepage +\input{temps} +\clearemptydoublepage +\part{Synthèse} +\input{manuel} +\clearemptydoublepage +\input{outils} +\clearemptydoublepage + +\chapter{Code source} +\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false} +\input{source} + +\clearemptydoublepage +\input{conclusion} +\clearemptydoublepage +\input{bib} +\clearpage +\strut\thispagestyle{plain} +\begin{tiny} +\begin{center} +Cette documentation a été réalisée sous Linux Slackware 7.1 à l'aide de \LaTeX\ et cvs. +\end{center} +\end{tiny} +\end{document} diff --git a/doc/algorithmes.tex b/doc/algorithmes.tex new file mode 100644 index 0000000..d4c43c5 --- /dev/null +++ b/doc/algorithmes.tex @@ -0,0 +1,57 @@ +\chapter{Algorithmes} +\section{Tas Binomial} +\paragraph{} +L'implémentation de certaines parties des algorithmes sur les tas binomiaux ont nécessité quelques changements, notemment +en ce qui concerne la gestion des cellules. En effet, il se pose un grave problème lors de l'implémentation de "DIMINUER-CLÉ", +car nous effectuons des changements dans les cellules. Et si l'appelant a gardé des pointeurs sur les cellules elles-mêmes, alors +leur contenu ne correspondra plus à la valeur d'insertion. Il faudrait pouvoir modifier aussi les pointeurs sur les cellules +qui ont été renvoyés à l'appelant, ce qui est impossible, vu que ces variables ne font pas partie de l'espace de données de notre +structure. +\paragraph{} +Pour résoudre ce problème, nous avons une table de pointeurs "tampon" qui vont stoquer les vrais pointeurs sur +les cellules du tas binomial. Comme ces pointeurs sont conservés dans la structure +de données, nous pouvons les modifier à loisir, lors d'une opération diminuer clef. Ainsi les pointeurs renvoyés à l'appelant +ne sont pas les pointeurs sur le tas directement, mais des pointeurs sur cette structure tampon, qui joue le role d'intermédiaire. +\paragraph{} +Cette structure est une liste doublement chaînée non triée (afin de pouvoir libérer la mémoire correctement +à la fin du programme), et vu que les deux seules opérations que nous effectuons dessus sont "INSERER" et "SUPPRIMER", nous ne +faisons que des opérations en $O(1)$ ce qui n'aura aucune influence sur le déroulement des algorithmes eux-mêmes. +\paragraph{} +L'implémentation de l'algorithme "FUSIONNER-TAS-BINOMIAUX" a été réalisé différemment de l'idée du cormen. En effet, le livre +suggérait de créer un troisième tas, et d'y placer les éléments de T1 et de T2 pour effacer T1 et T2 ensuite. Nous nous contentons +d'effectuer une fusion "sur place". C'est à dire nous vidons le tas T2 et nous insérons ses éléments à la bonne place dans le tas +T1. Ceci a pour but d'éviter la copie des cellules, pour la même raison que ci-dessus. Autant limiter les opérations et nous +contenter d'utiliser les blocs mémoires déjà alloués. +\paragraph{} +L'implémentation de l'algorithme "UNION" ne diffère que très légèrement de l'algorithme proposé, et nous obtenons un algorithme +légèrement plus simple. En effet, dans l'algorithme proposé, nous avons un cas particulier dans le cas où nos pointeurs se +trouvent en début de liste. Nous résolvons le problème directement car notre structure de données est récursive et le tas est +aussi une cellule de tas binomial. Ainsi, physiquement, nous ne commençons pas à la première, mais à la deuxième cellule du tas. +Le problème du cas particulier est donc réglé. +\section{Tas de Fibonacci} +\paragraph{} +Le tas de Fibonacci, quique d'allure complexe, n'a pas posé de problèmes d'implémentations particuliers. La seule particularité +fut d'implémenter certaines des phrases "en français dans le texte" telles que "parcourir la liste des pointeurs de base". Nous avons +aussi inversé en général l'ordre des choses lors de l'implémentation, ceci afin d'eviter de complexifier le code C++. En effet, +deux opérations consécutives peuvent influencer l'une sur l'autre, et mener à des situations de programmation délicates. Les +inverser peut présenter un aventage d'un point de vue conception, et n'influencer en rien le déroulement de l'algorithme. Le code +source des tas de Fibonacci est commenté de manière à pouvoir suivre les changements effectués lors de l'implémentation. +\paragraph{} +La seule restriction que nous avons posé fut sur l'algorithme "CONSOLIDER" pour lequel le tableau A possède une taille fixe. +En effet, nous ne pouvons évaluer à l'avance le nombre de case dont nous aurons besoin, sachant que certaines branches du +tas peuvent être dégénérées. +\section{Liste chaînée triée} +\paragraph{} +Cette implémentation n'a posé aucun problèmes particuliers, la structure étant extrèmement simple. La seule particularité qu'il +peut être amusant de souligner, est que l'algorithme "UNION" est en fait la partie "FUSION" de l'algorithme de tri fusion. +\section{Tas Binaire} +\paragraph{} +Comme pour le tas binomial, les cellules pouvant être échangées, nous ne pouvons renvoyer directement de pointeur sur le +tableau lui-même. De ce fait, nous avons utilisé exactement la même structure "tampon" que pour le tas binomial. +\paragraph{} +Le tableau dans lequel nous stoquons les valeurs n'est en aucun cas limité en revanche. Nous avons inclus un mécanisme qui +va redimentionner le tableau automatiquement en fonction des indices demandés, ce qui nous permet d'effectuer des tests +comme si la structure avait une dimension infinie. +\paragraph{} +Le reste de l'implémentation n'a posé aucun problème. Il est à noter en revanche qu'il a fallu inverser les conditions par rapport +à ce qui est décrit dans le livre. En effet, le tas binaire du livre nous donne une structure permettant d'effectuer "EXTRAIRE-MAX". diff --git a/doc/bib.tex b/doc/bib.tex new file mode 100644 index 0000000..1203fbb --- /dev/null +++ b/doc/bib.tex @@ -0,0 +1,7 @@ +\begin{thebibliography}{WWW99} +% pour citer le Tanenbaum : \cite{Tanenbaum} +% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum} + +\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction à l'algorithmique}, Dunod. + +\end{thebibliography} diff --git a/doc/conclusion.tex b/doc/conclusion.tex new file mode 100644 index 0000000..e5d9edf --- /dev/null +++ b/doc/conclusion.tex @@ -0,0 +1,9 @@ +\chapter*{Conclusion} +\addcontentsline{toc}{chapter}{Conclusion} +\markboth{CONCLUSION}{CONCLUSION} + +Ce projet a été mené à terme, et l'ensemble des conditions du sujet ont été respectées. +L'effort de recherche mené sur la manière d'implémenter les algorithmes en C++ a +sans aucun doute été profitable pour notre connaissance personnelle. De plus, les algorithmes +implémentés sont "durables": ils peuvent nous resservir dans n'importe quel autre projet nécessitant +des structures de files de priorités, ce qui porte un intérêt quant au développement de ce projet. diff --git a/doc/description.tex b/doc/description.tex new file mode 100644 index 0000000..e86c698 --- /dev/null +++ b/doc/description.tex @@ -0,0 +1,19 @@ +\chapter{Description} +\paragraph{} +Nous allons décrire dans cette première partie tous ce que nous avons effectué comme travail de réflexion afin de +programme ce projet. Il y a beaucoup de détails relatifs à l'implémentation dont nous ne parlerons pas, comme les structures +sur les listes chaînées, ou l'initialisation du terminal pour gérer le menu du programme de test. En revanche, nous appuyerons +sur les détails d'implémentation purement algorithmiques qui nous ont posé problème. +\paragraph{} +En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus +adapté pour créer les structures de données nécessaire à la programmation de ce projet. +\paragraph{} +Nous avons implémenté les algorithmes de files de priorités suivants: +\begin{itemize} +\item Tas Binaire +\item Tas Binomial +\item Tas de Fibonacci +\item Liste chaînée triée +\end{itemize} +\paragraph{} +L'algorithme utilisant les files de priorité implémenté est l'algorithme de compression de dictionnaire Huffman. diff --git a/doc/intro.tex b/doc/intro.tex new file mode 100644 index 0000000..46d0e3c --- /dev/null +++ b/doc/intro.tex @@ -0,0 +1,11 @@ +\chapter*{Introduction} +\addcontentsline{toc}{chapter}{Introduction} +\markboth{INTRODUCTION}{INTRODUCTION} + +\paragraph{} +Ce projet a pour but d'une part l'implémentation d'algorithmes de files de priorités et l'implémentation d'un algorithme +utilisant ces files de priorités d'autre part. + +\paragraph{} +Ce présent document va tenter de décrire en totalité la progression de la +mise en forme de ce projet. Nous vous souhaitons bonne lecture. diff --git a/doc/manuel.tex b/doc/manuel.tex new file mode 100644 index 0000000..fcdc3af --- /dev/null +++ b/doc/manuel.tex @@ -0,0 +1,124 @@ +\chapter{Manuel d'utilisation} +\paragraph{} +Ce projet génère deux binaire. Le premier appelé testTas n'est qu'une petite application nous permettant d'utiliser l'API +C++ générée par notre classe de file de priorités. Voici un exemple d'exécution: +\begin{verbatim} +Priority list type: 0 - Binary Heap +Choice: Please select an action +a - Add a key into the priority list +c - Change priority list type +d - Delete a Key from the priority list +e - Extract Min onto the priority list +l - Lower Key onto a key of the priority list +p - Print the current priority list on the screen +r - Remove the whole priority list +t - Test the priority list algorithms +q - Quit +\end{verbatim} + +A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La +fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas +pour y retrouver le pointeur d'un élément, le programme nous propose de sauvegarder le pointeur résultat dans un tableau: + +\begin{verbatim} +Choice: Please select a slot to save the cell +0 - Empty slot +1 - Empty slot +2 - Empty slot +3 - Empty slot +4 - Empty slot +5 - Empty slot +6 - Empty slot +7 - Empty slot +8 - Empty slot +9 - Empty slot +n - Don't store +c - Cancel +\end{verbatim} + +Ce tableau apparaitra régulièrement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes +les fonctions du menu parlent d'elles mêmes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la +file de priorité sélectionnée. + +\paragraph{} +Le deuxième binaire généré est 'Huffman'. Il sert à utiliser l'algorithme d'huffman implémenté. Voici sa ligne d'aide: +\begin{verbatim} +$ ./Huffman -h +Huffman [{-f|-i} file] {type} +Huffman -h +This will encode the input file with the Huffman code +using the priority list defined by type. +Type is a number taken from this list: + 0 : Binary Heap (default) + 1 : Binomial Heap + 2 : Fibonacci Heap + 3 : Sorted chained list +-f file means that you specify a dictionnary file which is + structured as described into the README file. +-i file means that you specify a file to encode. It will + built a quiet dumb dictionnary. +By default, a dictionnary will be built from stdin. +-h prints this help and exit. +\end{verbatim} + +La structure d'un dictionnaire est la suivante: +\begin{verbatim} +Mot1 : Fréquence1 +Mot2 : Fréquence2 +... +\end{verbatim} + +Chaque mot est une chaîne de caractères servant à identifier la fréquence associée. Voici un exemple complet de dictionnaire +et d'utilisation du programme avec ce dictionnaire: + +\begin{verbatim} +Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample +MOT1 : 2000 +MOT2 : 1234 +MOT3 : 15987 +MOT4 : 1203 +MOT5 : 192837 +MOT6 : 12987 +Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample +MOT3 (15987) = 00 +MOT1 (2000) = 0100 +MOT4 (1203) = 01010 +MOT2 (1234) = 01011 +MOT6 (12987) = 011 +MOT5 (192837) = 1 +Bitstream length : 283957 bits (= 35495 bytes) +Real size input : 7239936 bits (= 904992 bytes) +Size squeezed by : 96.0779 percents +Dictionnary size : 336 bits (= 42 bytes) +Total bitstream length : 284293 bits (= 35537 bytes) +Real gain (4 bytes header) : 96.0728 percents +\end{verbatim} + +Il est indiqué que le programme est capable de générer un dictionnaire à partir d'un fichier. Il s'agit simplement de compter +les caractères provenant de l'entrée et d'en générer un dictionnaire. Exemple: + +\begin{verbatim} +$ cat dict.sample | Huffman +\32 (12) = 00 +6 (1) = 01000 +4 (2) = 01001 +3 (4) = 0101 +0 (4) = 0110 +5 (2) = 01110 +7 (3) = 01111 +1 (6) = 1000 +M (6) = 1001 +: (6) = 1010 +\10 (6) = 1011 +O (6) = 1100 +8 (3) = 11010 +9 (3) = 11011 +2 (6) = 1110 +T (6) = 1111 +Bitstream length : 294 bits (= 37 bytes) +Real size input : 608 bits (= 76 bytes) +Size squeezed by : 51.6447 percents +Dictionnary size : 512 bits (= 64 bytes) +Total bitstream length : 806 bits (= 101 bytes) +Real gain (4 bytes header) : -38.1579 percents +\end{verbatim} diff --git a/doc/outils.tex b/doc/outils.tex new file mode 100644 index 0000000..69bbc53 --- /dev/null +++ b/doc/outils.tex @@ -0,0 +1,21 @@ +\chapter{Outils utilisés} +\paragraph{} +Pour développer ce projet, nous avons choisi d'utiliser une série d'outils GNU pour nous simplifier la tâche. +Nous utilisons entre-autres, GNU autoconf \& automake pour gérer notre arborescence de développement. Ainsi le +présent projet est découpé en ces répertoires: +\begin{itemize} +\item src contenant les sources des programmes exécutables. C'est notemment dans ce répertoire que seront stoqués +les binaires des exécutables produit par la compilation du projet. +\item lib contenant tous les sources purement algorithmiques, dont ne dépend pas l'implémentation finale. +\item include contenant tous les fichiers .h +\item doc contenant le source \LaTeX\ de cette présente documentation +\item po contenant les fichiers d'internationalisation (traduction française) +\item intl contenant le code source nécessaire au support de l'internationalisation. +\end{itemize} +En dehors de autoconf \& automake, nous avons utilisé un serveur CVS (Concurrent Version System) qui nous a permis +de travailler à plusieurs sur ce projet, sans avoir à nous soucier de rapatrier et de fusionner les codes sources +de tout le monde. +\paragraph{} +Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions. +Les binaires seront placés dans le répertoire src. Pour générer cette documentation, il suffit d'aller dans le répertoire doc +et de taper 'make ps'. diff --git a/doc/structures.tex b/doc/structures.tex new file mode 100644 index 0000000..c6c7013 --- /dev/null +++ b/doc/structures.tex @@ -0,0 +1,64 @@ +\chapter{Structures de données} +\section{Files de priorités} +Pour l'implémentation des files de priorités, nous avons remarqué que, comme pour des arbres ou des listes +chaînées, la structure est (dans le cas des tas Binomiaux et des tas de Fibonacci) récursive. Nous avons donc +choisi comme structure de données de base C++ une classe récursive. Qu'importe si les informations de récursivités +ne sont pas utilisés dans les autres dérivés de file de priorité. La classe implémentée est la suivante: + +\begin{lstlisting}{} +class PriorityList { + protected: + class GeneralException; + int type; + Key_t Key; + Datas_t Datas; + PriorityList(Key_t IKey, Datas_t const &IDatas); + + public: + PriorityList(void); + virtual ~ PriorityList(void); + + virtual Key_t ReadKey(Cell C); + virtual Datas_t ReadDatas(Cell C); + virtual int n(void); + virtual int rn(void) = 0; + + virtual void Dump(ostream & os) = 0; + virtual bool IsEmpty(void) = 0; + + virtual Cell Min(void) = 0; + virtual Cell Insert(Key_t IKey, Datas_t const &IDatas) = 0; + virtual Key_t Extract_Min(Datas_t & Datas) = 0; + virtual PriorityList *Union(PriorityList * P) = 0; + virtual bool Lower_Key(Cell x, Key_t NKey) = 0; + virtual Key_t Delete(Datas_t & Datas, Cell x) = 0; + PriorityList *GenericUnion(PriorityList * P); + int GetType(void); +}; +\end{lstlisting} + +Les types Key\_t, Datas\_t et Cell sont définis dans un include, et n'influencent en rien le comportement des algorithmes. +Il suffit que Key\_t soit un type "comparable" (nous avons mis int), et que Datas\_t et Cell soient capables de véhiculer +des informations. Pour ces deux derniers types, nous avons mis void *. A partir de cette classe de base, nous allons +dériver toutes les classes suivantes pour permettre l'implémentation des files de priorités. + +\section{Huffman} +Pour l'implémentation de l'algorithme de Huffman, nous avons eu besoin d'écrire une petite structure d'arbre toute simple: + +\begin{lstlisting}{} +class HTree { + private: + HTree * left, *right; + int freq; + char *objet; + public: + HTree(int n_freq, char *n_objet); + HTree(HTree * n_left, HTree * n_right); + ~HTree(); + ostream & Trace(ostream & os, int d = 0); + int ReadFreq(void); + char *ReadObj(void); +}; +\end{lstlisting} + +Notez au passage que la sturcture de données possède une fonction "trace" qui nous sert à générer visuellement le résultat de la compression. diff --git a/doc/temps.tex b/doc/temps.tex new file mode 100644 index 0000000..8763553 --- /dev/null +++ b/doc/temps.tex @@ -0,0 +1,26 @@ +\chapter{Analyse de temps} +\paragraph{} +L'analyse de temps n'est pas très difficile. En effet les différents temps sont déjà calculés pour ce qui est des +tas Binomiaux, des tas de Fibonacci et des tas binaires. Nous présenterons aussi les temps pour les files de priorités. +Voici donc les différents temps nécessaires pour les opérations de bases pour tous les algorithmes: +\paragraph{} +\begin{center} +\begin{tabular}{lcccc} +Procédure & Tas binaire & Tas binomial & Tas de Fibonacci & Liste chaînée triée\\ +\hline\\ +\textsc{Créer-Tas} & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$ & $\Theta(1)$\\ +\textsc{Insérer} & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\ +\textsc{Minimum} & $\Theta(1)$ & $O(\lg n)$ & $\Theta(1)$ & $\Theta(1)$\\ +\textsc{Extraire-Min} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\ +\textsc{Union} & $\Theta(n)$ & $O(\lg n)$ & $\Theta(1)$ & $O(n)$\\ +\textsc{Diminuer-Clé} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $\Theta(1)$ & $O(n)$\\ +\textsc{Supprimer} & $\Theta(\lg n)$ & $\Theta(\lg n)$ & $O(\lg n)$ & $\Theta(1)$\\ +\end{tabular} +\end{center} +\paragraph{} +Les temps de la liste chaînée triée sont simples à analyser et à expliquer. La liste étant triée et doublement chaînée, +les opérations MINIMUM, EXTRAIRE-MIN, et SUPPRIMER sont directes, donc en $\Theta(1)$. Ensuite, l'insertion doit trouver +le bon emplacement, donc parcourir au pire toute la liste chaînée afin d'effectuer l'insertion. C'est pourquoi l'opération +UNION est en $O(n)$. De même, l'opération DIMINUER-CLE va effectuer l'opération inverser, et déplacer l'élément vers la +gauche jusqu'à trouver sa nouvelle place, donc au pire va parcourir toute la liste. Ce qui nous fait des opérations en $O(n)$. +Enfin, l'opération UNION est l'implémentation de l'algorithme FUSIONNER du tri fusion. Nous avons donc un temps en $O(n)$ aussi. |