\chapterimage{tri.jpg}
\chaptertext{Un petit  chapitre qui sera le  bac à sable de  nos expériences sur
  la complexité...}

\chapter{Tris}


Dans toute la suite,  on se ramènera au cas du  tri d'une permutation quelconque
de $\mathfrak{S}_n$. On étudiera les
danses  hongroises   disponibles  en
ligne, par exemple: 


\href{https://www.youtube.com/watch?v=kDgvnbUIqT4}{https://www.youtube.com/watch?v=kDgvnbUIqT4}

\section{Tri sélectif...}

On parcourt la liste, on cherche le plus grand et on l'échange avec l'élément le
plus à droite et on recommence avec la liste privée du plus grand élément.

\subsection{Version impérative}

On commence  par chercher l'indice du  maximum d'une liste.  On part de 0  et on
compare à chaque élément  de la liste en faisant évoluer  l'indice du maximum si
nécessaire.

\begin{pythoncode}
def ind_maxi(xs):
    ind_tmp = 0
    n       = len(xs)
    for i in range(n):
        if xs[i] > xs[ind_tmp]:
            ind_tmp = i
    return ind_tmp
\end{pythoncode}


Ensuite, on copie la liste donnée en argument pour ne pas l'écraser. On parcourt
la liste et on  procède aux échanges éventuels entre le  maximum et l'élément de
droite.


\begin{pythoncode}
def tri_select(xs):
    cs = xs.copy()
    n  = len(cs)
    for i in range(n - 1,0,-1):
        i_m = ind_maxi(cs[:i + 1])
        if i_m != i:
            cs[i_m],cs[i] = cs[i],cs[i_m]
        # print(cs) : pour suivre l'évolution
    return cs
\end{pythoncode}

On  va utiliser  \Colorbox{blue!10}{\lstinline{permutation}} de  la bibliothèque
\Colorbox{blue!10}{\lstinline{numpy.random}}   qui   renvoie   une   permutation
uniformément choisie par les permutations de $\mathfrak{S}_n$.

\begin{pythoncode}
In [5]: ls = list(permutation(range(10)))

In [6]: ls
Out[6]: [8, 0, 4, 3, 5, 2, 7, 1, 9, 6]

In [7]: tri_select(ls)
[8, 0, 4, 3, 5, 2, 7, 1, 6, 9]
[6, 0, 4, 3, 5, 2, 7, 1, 8, 9]
[6, 0, 4, 3, 5, 2, 1, 7, 8, 9]
[1, 0, 4, 3, 5, 2, 6, 7, 8, 9]
[1, 0, 4, 3, 2, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Out[7]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
\end{pythoncode}



\subsection{Correction}

Il s'agit de démontrer la correction des deux fonctions. 

Pour  la  première,  l'invariant  de
boucle est: \og \lstinline{ind_temp}
est   l'indice    du   maximum   des
\lstinline{i + 1} premiers termes de
la  liste  en  argument\fg{}  et  se
démontre par récurrence.


Pour    la     deuxième    fonction,
l'invariant  de  boucle est  \og  la
liste  des élements  d'indices entre
\lstinline{i}  et \lstinline{n  - 1}
est triée\fg{}.



\subsection{Complexité}

Nous  mesurerons  la  complexité  en
nombre de comparaisons.

La           complexité           de
\Colorbox{blue!10}{\lstinline{ind_maxi(xs)}}
est en  $\Theta(n)$ avec $n$  la longueur
de
\Colorbox{blue!10}{\lstinline{xs}}.

En  effet, il  y a  une comparaison
par itération et $n$ itérations.


Pour
\Colorbox{blue!10}{\lstinline{tri_select}},
on  effectue  $n-1$  itérations,  et
chacune                        lance
\Colorbox{blue!10}{\lstinline{ind_maxi}}
sur une liste de longueur $i+1$.

Or
$\displaystyle\sum_{i=1}^{n-1}i+1=\sum_{i=2}^ni=(n-2)\frac{2+n}{2}=\frac{n^2-4}{2}$

donc la complexité est en $\Theta(n^2)$.

\begin{pythoncode}
In [10]: ls = list(permutation(100))

In [11]: %timeit tri_select(ls)
1000 loops, best of 3: 561 μs per loop

In [12]: ls = list(permutation(200))

In [13]: %timeit tri_select(ls)
100 loops, best of 3: 2.03 ms per loop

In [14]: ls = list(permutation(400))

In [15]: %timeit tri_select(ls)
100 loops, best of 3: 7.89 ms per loop
\end{pythoncode}

On  observe   effectivement  que  le temps  est environ  multiplié par  4
quand la taille de la liste double.



\section{Tri par insertion}

C'est le  tri d'un jeu de  carte: on
insère un élément dans un tableau trié petit à petit en comparant le
nouvel élément à insérer aux éléments
déjà triés.

La   version  récursive   est  assez
naturelle.   On  commence par  créer
une fonction qui insère
un nouvel élément dans la liste:

\begin{pythoncode}
def ins_rec(carte,Main):
    if Main == Vide or carte <= tete(Main):
        return [carte] + Main
    return [tete(Main)] + ins_rec(carte,queue(Main))
\end{pythoncode}


Ensuite,  pour trier,  on insère  la
tête dans la queue triée...

\begin{pythoncode}
def tri_ins_rec(Pioche):
    if Pioche == Vide:
        return Vide
    return ins_rec(tete(Pioche),tri_ins_rec(queue(Pioche)))
\end{pythoncode}


Pour la version itérative, on module
aussi:

\begin{pythoncode}
def insere(y,xs):
    cs = (xs.copy()) + [y] # xs est triée et on insère y par la doite
    n = len(xs)
    i = n
    while cs[i] < cs[i - 1] and i > 0:
        cs[i - 1], cs[i] = cs[i], cs[i - 1]
        i -= 1
        # print(cs)
    return cs

def tri_insere(Pioche):
    Main = Vide
    for carte in Pioche:
        Main = insere(carte, Main)
        #print(Main)
    return Main
\end{pythoncode}

La justification et la complexité de
ces fonctions seront à travailler en
TD, mais la complexité semble encore
quadratique:

\begin{pythoncode}
In [29]: ls = list(permutation(100))

In [30]: %timeit tri_insere(ls)
1000 loops, best of 3: 941 μs per loop

In [31]: ls = list(permutation(200))

In [32]: %timeit tri_insere(ls)
100 loops, best of 3: 3.67 ms per loop

In [33]: ls = list(permutation(400))

In [34]: %timeit tri_insere(ls)
100 loops, best of 3: 13.7 ms per loop
\end{pythoncode}





\section{Tri fusion}

Cette  fois,  si le  tableau a  au plus
une  valeur, il  est trié,  sinon on
coupe  le tableau  en deux,  on trie
ces deux moitiés et on fusionne.


\begin{pythoncode}
def tri_fusion(xs):
    t = len(xs) 
    if t < 2:
        return xs
    return fusion(tri_fusion(xs[:t//2]), tri_fusion(xs[t//2:])) 
\end{pythoncode}

Il reste à définir la fusion:

\begin{pythoncode}
def fusion(xs,ys):
    if xs == Vide or ys == Vide:
        return xs + ys
    if tete(xs) < tete(ys):
        return [tete(xs)] + fusion(queue(xs),ys)
    return [tete(ys)] + fusion(xs,queue(ys))
\end{pythoncode}


La  version récursive  est naturelle
mais pose toujours  des problèmes en
Python:  vous  chercherez  donc  une
version    impérative     à    titre
d'exercice...

L'étude  de  la terminaison,  de  la
correction et de la complexité devra
également  être   conduite  par  vos
soins.

Au fait:

\begin{pythoncode}
In [46]: ls = list(permutation(100))

In [47]: %timeit tri_fusion(ls)
1000 loops, best of 3: 296 μs per loop

In [48]: ls = list(permutation(200))

In [49]: %timeit tri_fusion(ls)
1000 loops, best of 3: 642 μs per loop

In [50]: ls = list(permutation(1000))

In [51]: %timeit tri_fusion(ls)
100 loops, best of 3: 3.88 ms per loop
\end{pythoncode}


\section{Tri rapide}



\subsection{Le tri et ses comlexités}

Observez et commentez:


\begin{pythoncode}
def partition(pivot,seq):
    p,m,g = [],[],[]
    for item in seq:
        (p if item < pivot else (g if item > pivot  else m)).append(item)
    return p,m,g

def tri_rapide(xs):
    if estVide(xs):
        return Vide
    else:
        pivot = tete(xs)
        p,m,g = partition(pivot, xs)
        return (tri_rapide(p)) + m + (tri_rapide(g))
\end{pythoncode}


Pour   la  complexité   en  moyenne,
montrez                          que
$$K(n)=n-1+\frac{1}{n}\sum_{i=0}^{n-1}(K(i)+K(n-1-i))$$

et en déduire que $$\frac{K(n)}{n+1}=2\sum_{i=2}^n\frac{i-1}{i(i+1)}$$


Que se passe-t-il dans le pire des cas?


Dans quel cas est-on sûr que le tri en $n\log n$?

\subsection{La médiane en temps linéaire}

Il serait très  pratique d'avoir une
médiane  en   temps  linéaire:  nous
aurions  alors  un   tri  rapide  en
$n\log n$ dans le pire des cas.


La  médiane  d'un   tableau  de  $n$
éléments   est  l'élément   de  rang
$\lfloor \frac{n+1}{2}\rfloor$ comme
vous l'avez appris au collège. 

L'idée est bien sûr d'éviter de trier le tableau pour trouver la médiane :-)

On  cherche  donc le  tableau  de  rang  $r_m=\lfloor \frac{n+1}{2}\rfloor$:  on  va
utiliser  la  fonction \lstinline{partition}  en  la  modifiant légèrement  pour
qu'elle renvoie  l'indice du  pivot après  partition. Si cet  indice est  égal à
$r_m$  on a  gagné, s'il  est plus  petit on  cherche la  médiane sur  la partie
droite, sinon sur la partie gauche.


Y a plus qu'à...





\vfill

\eject




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}

\includepdf[openright=false,pages={1-6},pagecommand={}]{X2012}



\begin{exercice}[Stupid Sort]

Que pensez-vous de  la complexité de
cet  algorithme  de tri? %  présenté  et
% expliqué ci-dessous? 

(source: \href{http://unclecode.blogspot.tw/2012/02/stupid-sort\_2390.html}{http://unclecode.blogspot.tw/2012/02/stupid-sort\_2390.html}):



\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{cpp}
void StupidSort()
{
    int i = 0;
    while(i < (size - 1))
    {
           if(data[i] > data[i+1])
          {
                int tmp   = data[i];
                data[i]   = data[i+1];
                data[i+1] = tmp;
                i = 0;
          }
          else
         {
               i++;
         }
     }
}
\end{minted}

\pythonc
\end{exercice}




\begin{exercice}[Trois-sommes amélioré]
  Maintenant que vous savez trier et rechercher dichotomiquement, donnez un algo
  \og  Trois_Sommes\fg{}  en  $n^2\log(n)$  sur  des  tableaux  considérés  sans
  doublons.

  (\textit{\small Cherchez des racines...})
\end{exercice}




\begin{exercice}[Trois-sommes: variante]

On considère  trois ensemble d'au maximum  N entiers. Déterminez q'il  existe un
triplet de $A\otimes B\otimes C$ tel que $a+b+c=0$.


  % Sort  B in increasing order;  sort C in decreasing  order; for each a  in A,
  % scan B and C for a pair that sums to -a (when the sum is too small, advance in
  % B, when the sum is too large, advance in C).  
\end{exercice}



\begin{exercice}[Mélange de cartes: le mélange de ASF Software]

Savoir bien trier c'est aussi savoir bien mélanger.
  
Afin de convaincre  les utilsateurs que leur algorithme de  mélange était juste,
la société ASF Software, qui produit les logiciels utilisés par de nombreux sites
de jeu, avait publié cet algorithme:

\begin{minted}[breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,linenos,fontfamily=txtt]{delphi}
procedure TDeck.Shuffle;
var
    ctr: Byte;
    tmp: Byte;

    random_number: Byte;
begin
    { Fill the deck with unique cards }
    for ctr := 1 to 52 do
        Card[ctr] := ctr;

    { Generate a new seed based on the system clock }
    randomize;

    { Randomly rearrange each card }
    for ctr := 1 to 52 do begin
        random_number := random(51)+1;
        tmp := card[random_number];
        card[random_number] := card[ctr];
        card[ctr] := tmp;
    end;

    CurrentCard := 1;
    JustShuffled := True;
end;
\end{minted}


\begin{enumerate}
\item  Considérez un  jeu de  3  cartes. Dressez  l'arbre de  tous les  mélanges
  possibles en suivant cet algorithme. Que remarquez-vous?
\item  Proposez  un   algorithme  qui  corrige  ce   problème.  Dressez  l'arbre
  correspondant pour un jeu de trois cartes.
\item Traduisez la fonction proposée en Python puis votre version corrigée en Python.
\end{enumerate}
\end{exercice}

\begin{exercice}[Tri rapide]
Explorez les  parties non développées en  cours sur le tri  rapide, notamment la
recherche de la médiane.


  
\end{exercice}


\begin{exercice}[Yet another sort of sort]

  \begin{algo}
\FOR{i}{1}{n}
\FORSTEP{j}{n}{i+1}{-1}
\IF{t[j]<t[j-1]}
\STATE{Échange t[j] et t[j-1]}
\ENDIF
\ENDFOR
\ENDFOR
  \end{algo}
  

Qu'est-ce que  c'est? Qu'est-ce que ça  fait? Comment ça marche?  Complexité? En
python? Donnez un nom à ce tri.

\end{exercice}


\begin{exercice}[Comparaisons de tris et révisions sur le tracé de graphiques]
  Tracez sur un même graphique les temps d'exécution des tris étudiés en fonction de la
  longueur d'une liste \og mélangée\fg{}.

  Sur un  autre graphique, comparez ces  tris avec des listes  ordonnées dans le
  sens croissant, puis avec des listes ordonnées dans le sens décroissant.

Pour cela, voici quelques rappels sur Matplotlib.

On lance  ipython avec l'option \Colorbox{blue!10}{\lstinline{-pylab}}  ou bien,
si  vous ne  travaillez  pas  dans un  confortable  terminal  Unix, vous  pouvez
toujours importer la chose:

\begin{pythoncode}
In [29]: import matplotlib.pyplot as plt

In [30]: p1 = plt.plot([1,2,3,4,5],[1,2,5,8,3], marker = 'o',label = "Idiot")

In [31]: p2 = plt.plot([1,2,3,4,5],[3,8,2,6,-1], marker = 'v',label = "Stupide")

In [32]: plt.legend()
Out[32]: <matplotlib.legend.Legend at 0x7fbc2c6b76d8>

In [33]: plt.title("Essai idiot")
Out[33]: <matplotlib.text.Text at 0x7fbc2babc668>

In [34]: plt.xlabel("Le temps")
Out[34]: <matplotlib.text.Text at 0x7fbc2c620898>

In [35]: plt.ylabel("C'est de l'amour")
Out[35]: <matplotlib.text.Text at 0x7fbc2baaa2b0>

In [36]: plt.show()

In [37]: plt.savefig("zig.pdf")

In [38]: plt.clf()
\end{pythoncode}


%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{zig}
\end{center}
%\end{figure}


Comment      mesurer     le      temps?     On      utilise     la      fonction
\Colorbox{blue!10}{\lstinline{perf_counter}}         de          la         bibliothèque
\Colorbox{blue!10}{\lstinline{time}}:



\begin{pythoncode}
from time import perf_counter

def temps(tri,p):
    debut = perf_counter()
    tri(p)
    return perf_counter() - debut
\end{pythoncode}

On devrait obtenir:


%\begin{figure}
\begin{center}
  \includegraphics[height=10cm]{benchmark}
\end{center}
%\end{figure}

et en regardant les trois plus rapides:


%\begin{figure}
\begin{center}
  \includegraphics[height=10cm]{benchmark2}
\end{center}
%\end{figure}

mais si les listes sont déjà rangées:




%\begin{figure}
\begin{center}
  \includegraphics[height=10cm]{benchmark3}
\end{center}
%\end{figure}

Comme le nombre d'appels récursifs va augmenter, on va augmenter aussi le nombre
d'appels récursifs autorisé:

\begin{pythoncode}
from sys import setrecursionlimit
setrecursionlimit(100000)
\end{pythoncode}

\end{exercice}

\modenormal
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2014_15"
%%% End: 
