\input{../.headers/cours.tex}

\section{Algorithme naïf}

\subsection{Description}

\begin{enumerate}
	\item Pour $i$ de 1 à $(n-1)$ 
	\begin{enumerate}
		\item Pour $k$ de $i+1$ à $n$ 
			\begin{enumerate}
		\item Si $\sigma(i) > \sigma(k)$ on rajoute une inversion.
			\end{enumerate}
	\end{enumerate}
\end{enumerate}

\subsection{Complexité}

$O(n^2)$ car $\sum_{k=1}^{n} k$ comparaisons.

\subsection{Implémentation}

\begin{minted}{ocaml}
let count_inversions sigma =
	let rec inloop sigma_i sigmas = match sigmas with
		| []   -> 0
		| h::t -> if h < sigma_i 
			then 1 + (inloop sigma_i t)
			else (inloop sigma_i t)
		in
	let rec outloop sigmas = match sigmas with
		| []   -> 0
		| [a]  -> 0
		| h::t -> (outloop t) + inloop h t
		in
	outloop sigma;;
\end{minted}

Le test:

\begin{minted}{ocaml}
assert (count_inversions [2;4;3;1;5] = 4)
\end{minted}

\section{Algorithme de fusion}
\subsection{Description}

\paragraph{Un example}

\[
	\begin{cases}
		1 \mapsto 5 \\
		2 \mapsto 2 \\
		3 \mapsto 1 \\
		4 \mapsto 3 \\
		5 \mapsto 4 \\
	\end{cases} = \text{\mintinline{ocaml}|[5; 2; 1; 3; 4]|} \quad\text{5 inversions}
\] 

On coupe: \ocaml{[5; 2; 1]} et \ocaml{[3; 4]}.

Trions \ocaml{[5; 2; 1]}.

\begin{itemize}
	\item On échange \ocaml{1}
	\item On fusionne \ocaml{[5]} et \ocaml{[1; 2]}
	\item \ocaml{[1; 2; 5]}
\end{itemize}

Trions \ocaml{[3; 4]}

\paragraph{Un autre exemple}

\[
	\ocaml{[5; 3; 1; 2; 4]}
\] 



\paragraph{En gros}
On incrémente un compteur quand il faut inverser tout en triant la liste par fusion.

\subsection{Compléxité}

\begin{description}
	\item[Tri par fusion] $\Theta(n \log_2 n)$
	\item[Compte de permutation] 
\end{description}

\subsection{Implémentation}

\begin{minted}{ocaml}
let split l = 
	let rec aux l n acc = match l with
	| [] -> [], []
	| h::t when n=0 -> (List.rev acc, h::t)
	| h::t -> aux t (n-1) (h::acc)
	in aux l (List.length l / 2) [];;

let merge l1 l2 = 
let rec aux l1 l2 _acc = match l1, l2 with
| [], _ -> l2
| _, [] -> l1
| h1::t1, h2::t2 -> if h1 < h2
	then h1::(aux t1 l2 _acc)
	else h2::(aux l1 t2 (_acc + List.length l1))
in aux l1 l2 0;;
\end{minted}

\end{document}