\section{Tri rapide}

A début des années 60, C.A.R. Hoare\footnote{Inventeur de la
logique du même nom!} a
publié un article concernant l'analyse
d'une méthode de tri connue sous le nom
de \algo{quick sort}, une copie de cet
article est sur le site du cours.

\subsection{description}

L'algorithme présenté ici est tiré de
l'ouvrage du bijectioniste Herbert Wilf \cite{WH}, 
dont une version est disponible sur la toile à partir
des mots clefs : \kws{wilf}, \kws{herbert},
\kws{complexity},\kws{algorithm}. 

\begin{lstlisting}[float, style=algo, title={quick sort}]
procedure qksort(x:array; left, right:integer);
{sorts the subarray x[left], . . . , x[right]}
 if right - left >= 1 then
	p := split( x, left, right )
	qksort(x, left, p - 1);
	qksort(x, p + 1, right)
end.{qksort}
\end{lstlisting}

Il
utilise le principe algorithmique
{\sl diviser pour régner} pour décomposer le
travail du tri de taille (left - right + 1)
en deux tâches de taille respective 
(left - $i$) et ($i$ -right). La procédure
\algo{split} déplace les éléments du sous-tableau
et retourne un pivot $p$ vérifiant :
$$
\forall k\leq p,\quad x[k] \leq x[p]; 
\qquad
\forall k\geq p, \quad x[k] \geq x[p]. 
$$

Un raisonnement inductif s'appuyant sur
la condition  qui précéde fournit sur le
champ preuve une preuve de correction de
l'algorithme.
 
Il existe plusieurs implantations de
recherche de pivot, elles sont toutes
linéaires.

\subsection{décomposition de Lomuto}

La décomposition de Lomuto est facile à prouver.
\begin{proof}
Pour un tableau indexé par les entiers de $l$ à $r$,
elle s'appuie sur l'invariant :
$$
x[ l ] = T,
\qquad
\forall k\leq i,\quad x[k] <  T
\qquad
\forall k,\quad i< k \leq j,\quad x[k]\geq T.
$$
\end{proof}

\begin{center}
\begin{figure}
\includegraphics[scale=0.5]{img/lomuto.png}
\end{figure}
\end{center}

\begin{lstlisting}[float, style=algo, numbers=left, title=Lomuto]
procedure split(x, left, right, i)
T := x[left];
i := left;
for j := left + 1 to right do
  if x[j] < T  then
	i := i + 1
	swap(x[i], x[j])
  fi
done
swap(x[left], x[i])
end. {split}
\end{lstlisting}


\lstinputlisting[style=gcc, firstline=25, lastline=50, 
title={un exemple de tri rapide}]{src/rapide.c}

\begin{lstlisting}[language=Make]
rapide.png : rapide.c
	gcc -Wall -g rapide.c 
	./a.out 'PROCEDURE DE PARTITION'  > rapide.dot
	dot -Tpng rapide.dot -o rapide.png
\end{lstlisting}

\begin{figure}
\includegraphics[scale=0.3]{src/rapide.png}
\caption{\label{PART} L'arbre des divisions
du tri rapide en action. 
}
\end{figure}

\begin{exercice}
Proposer un invariant pertinent pour
la boucle \gcc{for} de la procédure
de division de \gcc{rapide.c}.
\end{exercice}

\subsection{Temps de calcul}
 
\subsubsection{cas défavorable}

La fonction de coupure retourne toujours un
élément extrémal. En notant $L(n)$ le temps
de coupure, il existe une constante $K$ 
telle que
\begin{equation}
	T(n) = T(n-1) + L(n) + K
\end{equation}

Au final, un temps de calcul quadratique.

\subsubsection{fonctionnement idéal}

La fonction de coupure retource un indice
médian. En supposant que $n$ est une 
puissance de $2$

\begin{equation}
       T(n) = 2 T(n/2) + L(n) + K
\end{equation}

Au final, un temps de calcul de
l'ordre de  $n\log_2 n$.

\subsubsection{cas moyen}

Notons $C(n)$ le nombre moyen de comparaisons
effectuées par \algo{split} satisfait la relation
$$
	C(n)   = (n-1) + \frac 2n \sum_{k=1}^{n-1} C(n-k).
$$

On peut deviner la forme de $C$ en supposons une
fonction à croissance raisonnable, et en utilisant
la technique de comparaison d'une série avec une
intégrale

$$
	C(x)   = x + \frac 2x \int_1^x C(t) {\rm d}t,
$$

qui conduit à l'équation différentielle

\begin{align*}
	C'(x)  &= 1 - \frac 2{x^2} \int_1^x C(t) {\rm d}t + 2C(x)/x\\
               &= 1 - \frac 1x  (C(x) -x ) + 2C(x) /x\\
               &= 2 + C(x) /x\\
\end{align*}

dont la solution générale est $2 x\log x$ plus
un terme linéaire. Cela dit, on peut tout aussi 
bien s'en tirer par un calcul direct 

\begin{align}
	C(n)   &= (n-1) + \frac 2n \sum_{k=1}^{n-1} C(n-k)\\
	C(n-1) &= (n-2) + \frac 2{n-1} \sum_{k=1}^{n-2} C(n-1-k)\\
\end{align}

D'où l'on tire que
$$
      n C(n) - (n-1) C(n-1)    = 2 C(n-1) + n(n-1) - (n-1) (n-2)
$$
soit
$$
      n C(n) = (n+1)  C(n-1) + 2 (n-1)
$$
et donc que $F(n) := \frac{C(n)}{n+1}$ satisfait la 
relation assez conviviale

\begin{align*}
       F(n) &= F(n-1) +  2 \frac{n-1}{n(n+1)}\\ 
            &= F(n-1) + 2 ( \frac{1}{n} - \frac{1}{n(n+1)} ) \\ 
\end{align*}

La série  de terme général $\frac{1}{n(n+1)}$ converge, il
suit que~:
\begin{equation}
       C(n) \sim 2 n H(n) \sim 2 n \log(n) 
\end{equation}

où $H(n)$ désigne la série Harmonique, en particulier, c'est
bien un logarithme népérien qui apparaît dans la formule. 

\subsection{Optimisation}


\subsubsection{seuil}

Un appel récursif a toujours un coût : sauvegarde de contexte,
empilage et dépilage des paramètres, retour et restauration de
contexte. Pour une instance de petite taille, il est péférable 
d'utiliser une méthode directe : un tri par insertion.

\subsubsection{Elimination de la récursivité}

Un algorithme de tri rapide s'appuie sur un
parcours d'arbre binaire. Il est assez facile de
supprimer la récursivité c'est-à-dire gérer une
pile à la main pour optimiser le code.


\subsubsection{la fonction \gcc{qsort}}


Un tri rapide est disponible dans la bibliothèque
standard. Vous pouvez vérifier, d'une part, qu'il 
s'agit bien de la fonction utilisée par la commande 
\shell{sort}, et que, d'autre part,  les deux optimisations 
précédentes sont mises en oeuvre.


\begin{lstlisting}[style=term]
tri> which sort
/usr/bin/sort

tri> objdump -T  /usr/bin/sort  | grep qsort
00000000      DF *UND*	00000000  GLIBC_2.0   qsort

tri> git clone git://sourceware.org/git/glibc.git

tri> grep -iEB3 'def.*thres' glibc/stdlib/qsort.c

/* Discontinue quicksort algorithm when partition 
gets below this size.This particular magic number 
was chosen to work best on a Sun 4/260. */
#define MAX_THRESH 4
\end{lstlisting}


\begin{lstlisting}[float, style=man]
QSORT(3)        Linux Programmer's Manual
NAME
       qsort, qsort_r - sort an array
SYNOPSIS
       #include <stdlib.h>

   void qsort(void *base, size_t nmemb, size_t size,
            int (*compar)(const void *, const void *));
DESCRIPTION
       The  qsort()  function sorts an array with nmemb 
 elements of size size. The base argument points to the 
 start of the array.
\end{lstlisting}

\begin{lstlisting}[float, style=gcc]
// example from man qsort
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int
   cmpstringp(const void *p1, const void *p2)
   {
 /* The actual arguments to this function are "pointers 
 * to pointers to char", but strcmp(3) arguments are 
 * "pointers to char", hence the following cast plus 
 * dereference 
 */
   return strcmp(* (char * const *) p1, 
                             * (char * const *) p2);
   }
int main(int argc, char *argv[])
 {
 int j;

 if (argc < 2) {
    fprintf(stderr, "Usage: %s <string>...\n", argv[0]);
    exit(EXIT_FAILURE);
    }

 qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);

 for (j = 1; j < argc; j++) puts(argv[j]);
      exit(EXIT_SUCCESS);
 }
\end{lstlisting}

\subsection{borne minimale}

A l'image du tri \shell{timesort}, ou plus sérieusement
du tri linéaire, un algorithme  de tri n'est pas toujours 
fondé sur la comparaison des objets qu'il doit trier !

\lstinputlisting[style=bash, title=timesort]{src/timesort.sh}


\begin{theoreme}
Le temps de calcul de d'un algorithme de tri 
comparatif est de  complexité $\Omega( n \log n )$.
\end{theoreme}
\begin{proof}
\end{proof}

Le théorème affirme donc l'impossiblité de trouver
un algorithme de tri comparatif  plus performant 
que le tri rapide.


\subsection{exercice}

\subsubsection{tri linéaire}

Le tri d'une table de taille $n$ de nombres positifs
inférieurs à un entier $m=\bigo( n )$ est réalisable
en temps linéaire.

Il suffit d'utiliser un tableau auxiliaire de taille
$m$ pour compter le nombre d'occurrences des valeurs
de $t$.

\begin{exercice}
Ecrire une fonction \gcc{void trilin(int* t, int n)}
pour trier un tableau de taille $n$ sachant que la plus
grande valeur de $t$ est $\bigo(n)$.
\end{exercice}
