# Correction TD2

### Partie 2

Voir les déroulages concrets et abstraits (avec les $\blacklozenge$) [ici](https://uniren1.sharepoint.com/:x:/s/L1PortailIE-SI1/EVlH92WXBAlLjosTVV38lVoBmEbfmWFR7keri41YhyDDNA?e=HE2tgS).

1. complexité de l'algorithme de recherche (A)

* Le pire cas est quand on recherche un élément qui n'est pas dans le tableau. Déroulons l'algorithme (A) pour les 2 pires cas de taille N=3 (cherche=7 et t={4,5,12}) et N=4 (cherche= 25, t={2,8,12,14}).
* A partir des déroulages concrets on produit les déroulages abstraits.
* Dans les déroulages abstraits, pour N=3 on a 5 losanges et pour N=4 on a 6 losanges. On peut en déduire que $f(N)= N+2$. Donc la complexité de l'algorithme est en $O(f(N))= O(N+2)= O(N)$
2. complexité de l'algorithme de recherche (B)

* Le pire cas est quand on recherche un élément qui n’est pas dans le tableau et supérieur à la valeur maximale du tableau. Déroulons l’algorithme (B) pour le pire cas de taille N=2 (cherche=8 et t={4,5}) et de taille N=3 (cherche=14 et t={4,8,12} ).

* A partir des déroulages concrets on produit les déroulages abstraits.

* Dans les déroulages abstraits, pour un tableau de taille N = 3 on a 5 losanges et pour N=2 , on a 4 losanges. On peut en déduire que $f(N)=N+2$. Donc la complexité de l'algorithme est en $O(f(N))=O(N+2)=O(N)$.

3. complexité de l'algorithme de recherche ( C)

Rappel: Si on note $log_2(N)$ la partie entière du logarithme (base 2) de $N$, alors $log_2(N)+1$ est le nombre de fois que l'on peut diviser $N$ par $2$ jusqu'à atteindre 0. Par exemple, pour $N=5$, $log_2(5)+1=3$ et $5/2=2$, $2/2=1$ et $1/2=0$.

5. complexité des algorithmes modifiés au TD1
par exemple...

public static int nbOccurrences(int cherche, int[] t){
    int k= 0;
    int i=0;
    while(i<t.length && t[i]<=cherche){
        if(t[i]== cherche) {
            k++
        }
        i++;
    }
    return k;
}

## Partie 3

1. tri **sélection**

// Echange de 2 valeurs dans le tableau t aux positions i et j
public static void swap( int[] t,int i,int j) { 
    int tmp = t[i];
    t[i]=t[j];
    t[j]=tmp;
}
    
public static void tri2(int[] t) {
    for(int i=0;i<t.length;i++) {
        int min=i;
        for(int j=i+1;j<t.length;j++) {
            if(t[j]<t[min]) {
                min=j;
            }
        }
        swap(t,i,min);
    }
}

#### Analyse de complexité du tri sélection ```tri2```

* Ce tri parcourt l'intégralité du tableau quel que soit l'ordre des éléments dans le tableau et appellera l'échange (swap) même s'il est inutile. En revanche la condition ```if (t[j]<t[min])``` ne sera exécutée que si les éléments sont dans le désordre. Comme pire cas pour $N=3$, vous avez proposé le tableau ```t={5,2,1}```. Comme pire cas pour $N=2$, vous avez choisi ```t={5,2}```. Pour $N=3$ pourquoi ```t={5,2,1}``` et ```t={5,1,2}```... en fait ce sont tous les deux des pires cas:
* Pour le tableau ```t={5,2,1}```, on peut remarquer (dans le déroulage) que lors de la première itération la valeur du minimum va changer 2 fois mais qu'elle ne va pas changer une seule fois lors de la seconde itération car en échangeant 1 et 2 on obtient directement le tableau trié ```t={1,2,5}```.
* Dans le cas du tableau ```t={5,1,2}```, la première itération ne va changer qu'une fois le minimum et à la sortie de la première itération le tableau sera ```t={1,5,2}``` qui n'est toujours pas trié. Cependant lors de la seconde itération le minimum ne changera qu'une fois. Donc considérer le tableau ```t={5,2,1}``` ou ```t={5,1,2}``` nous place dans les deux cas dans un pire cas. Gardons ```t={5,2,1}```.
* Dans le pire cas pour $N=3$ et $N=2$ on a respectivement:
* Pour $N=2$ on a $f(2) = 2+1 + \:\:\: 3$ losanges
* Pour $N=3$ on a $f(3) = 3+2+1 + \:\:\:4$ losanges
Donc $f(N)= (N+1)+N+\ldots + 1$. On sait que $1+2+ \ldots + N = \frac{N \times (N+1)}{2}$. Donc, on en déduit que $f(N) = \frac{(N+1) \times (N+2)}{2}$. La complexité de notre ```tri2``` est en $O(f(N))$. Si on développe $f(N)$, on obtient $f(N)= \frac{N^2+2N+N+2}{2} = \frac{1}{2}N^2+\frac{3}{2}N+1$. La complexité de ```tri2``` est donc en $O(\frac{1}{2}N^2+\frac{3}{2}N+1)$. Par la propriété 1 du cours, on peut simplifier cela en:
$\begin{align} O(\frac{1}{2}N^2+\frac{3}{2}N+1)
& = O(\frac{1}{2}N^2+\frac{3}{2}N) \\
&= O(\frac{1}{2}N^2)\\
&= O(N^2)\end{align}$
Pour finir, la complexité de ```tri2``` est donc $O(N^2)$.

#### Analyse de complexité du tri sélection ```triSelection```

public static void triSelection(int[] tab) {
    int IndiceMin =0;
    int mem=0;
    for(int i=0; i<tab.length-1; i++) {
           IndiceMin=i;
           for(int j=i+1; j<tab.length; j++) {
                if(tab[j]<tab[IndiceMin])
                    IndiceMin=j;
            }
            if(IndiceMin!=i) {
                mem=tab[i];
                tab[i]=tab[IndiceMin];
                tab[IndiceMin]=mem;
           }
      }
  }

* Par rapport au précédent, ce tri parcourt l'intégralité du tableau (moins une case!) quel que soit l'ordre des éléments dans le tableau. Il n'utilisera l'échange que si celui-ci est utile. Les pires cas en revanche ne changent pas par rapport à ```tri2```. Celui-qui a été utilisé pour les déroulages est```t={5,1,2}```.

* Dans le pire cas pour $N=3$ et $N=2$ on a respectivement:
* Pour $N=2$ on a $f(2) = 2+1 + \:\:\: 2$ losanges
* Pour $N=3$ on a $f(3) = 3+2+1 + \:\:\:3$ losanges
Donc $f(N)= N+N+(N-1)+\ldots + 1 +$. On sait que $1+2+ \ldots + N = \frac{N \times (N+1)}{2}$. Donc, on en déduit que $f(N) = N+\frac{N \times (N+1)}{2}$. La complexité de ```triSelection``` est en $O(f(N))$. Si on développe $f(N)$, on obtient $f(N)= N+\frac{N^2+N}{2} = \frac{1}{2}N^2+\frac{3}{2}N$. La complexité de ```tri2``` est donc en $O(\frac{1}{2}N^2+\frac{3}{2}N)$. Par la propriété 1 du cours, on peut simplifier cela en:
$\begin{align} O(\frac{1}{2}N^2+\frac{3}{2}N)
&= O(\frac{1}{2}N^2)\\
&= O(N^2)\end{align}$
Pour finir, la complexité de ```triSelection``` est donc $O(N^2)$.

Encore une autre version de tri sélection... très proche de la précédente. Je vous laisse l'analyser :-)

public static void triMinimum(int[] t) {
    int min = 0;
    int save = 0;
    for(int i=0; i<t.length-1; i++) {
        min = i;
        for(int i2=i+1;i2<t.length;i2++) {
            if(t[i2]<t[min]) {
                min = i2;
			}
        }
        save = t[i];
        t[i] = t[min];
        t[min] = save;	
    }
}

2. tri **insertion**

Tri insertion en une seule fonction.
Est-ce que ce tri est correct? (a priori oui?)

public static void triInsertion(int[] tab) {
    for(int i = 1; i < tab.length; i++) {
        int n = tab[i];
        int j = i;
        while (j > 0 && tab[j - 1] > n) {
            tab[j] = tab[j - 1];
            j = j - 1;
        }
        tab[j] = n;
    }
}

#### Analyse de complexité de ```triInsertion```
* Le tri par insertion construit progressivement un tableau trié de l'indice 0 à l'indice i et y insère l'élément i+1, le pire cas est donc quand on doit redécaler tous les éléments entre 0 et i pour y insérer le i+1 ème. Le pire cas est donc quand le tableau est trié en ordre inverse. On choisit ici pour $N=2$ le tableau ```tab={2,1}```, pour $N=3$ le tableau ```tab={5,2,1}```, et pour $N=4$ le tableau ```tab={5,2,1,0}```.
*
* Dans le pire cas pour $N=2$, $N=3$ et $N=4$ on a respectivement
* Pour $N=2$ on a $f(2) = 2+1 + \:\:\:\: {\color{red}1}$
* Pour $N=3$ on a $f(3) = 3+2+1 + \:\:\:\: {\color{red}2}$
* Pour $N=4$ on a $f(4) = 4+3+2+1 + \:\:\:\:\: {\color{red}3}$
Par ailleurs, on sait que $1+2+ \ldots + N = \frac{N \times (N+1)}{2}$. On en déduit que $f(N) = \frac{N \times (N+1)}{2} + (N-1)$. La complexité de ```triInsertion``` est en $O(f(N))$. Si on développe $f(N)$, on obtient $f(N)= \frac{1}{2} N^2 + \frac{1}{2}N + (N-1) = \frac{1}{2}N^2 + \frac{3}{2} N -1$. La complexité de ```triInsertion``` est donc $O(\frac{1}{2}N^2 + \frac{3}{2} N -1)$. Par la propriété 1 du cours, on peut simplifier cela en:
$\begin{align} O(\frac{1}{2}N^2+\frac{3}{2}N-1)
&= O(\frac{1}{2}N^2+\frac{3}{2}N)\\
&= O(\frac{1}{2}N^2)\\
&= O(N^2)\end{align}$
Pour finir, la complexité de ```triInsertion``` est donc $O(N^2)$.

#### Analyse de complexité de ```triInsertion2```
Autre version en deux fonctions.

// A partir d'un tableau t et d'une position index, 
// insertion de l'élément t[index] dans le sous-tableau trié
// t[0;index-1]
public static void insertion(int index, int t[]){
	int j= index-1;
	while(j>=0 && t[j]>t[j+1]){
		swap(t,j,j+1);
		j=j-1;
	}
}

// tri par insertion
public static void triInsertion2(int[]t){
	for (int i=1; i<t.length; i++){
		insertion(i,t);
	}
}

Je ne vais pas détailler les déroulages et l'analyse complète de cette version (je vous laisse le faire). Mais l'analyse de complexité peut se réaliser fonction par fonction (c'est un peu ce qu'on vous demande en TP dans les comptes rendus).
* fonction ```insertion``` dans le pire des cas, on insère l'élément en début de tableau, donc on itère $N$ fois le ```while``` (si $N$ est la taille du tableau). Dans le while on appelle la fonction ```swap``` qui réalise exactement 3 instructions et ce quelle que soit la taille du tableau (sa complexité est en $O(1)$) et on réalise ```j=j-1``` soit une instruction. Moralité dans le corps du while on réalise un nombre constant d'instructions : 4 (c'est indépendant de $N$) ! La complexité de ```insertion``` est donc en $O(N)$.
* fonction ```triInsertion2``` dans le pire des cas, on itère $N-1$ fois la fonction ```insertion``` qui a, comme on l'a vu au dessus, une complexité $O(N)$. Au final la complexité de ```triInsertion``` sera donc en $O(N^2)$.

5. tri **bulle**

Est-ce que ce tri est correct? (Comment le simplifier et supprimer le doublon flag/chk?)

public static void triBulle(int[] t) {  // trier tableau int[] t  ( complexite n^2)
    boolean flag = false;		// pour arreter boucle while
    while (!flag) {
        int chk = 0;			// verifier dans un boucle trie
        for(int i=0;i<t.length-1;i++){
            if(t[i]>t[i+1]) {
                swap(t,i,i+1);
                 chk++;
            }
        }
        if (chk ==0) {
            flag=true;
         }
    }
}

Version sans le doublon "flag/chk"

public static void triBulle(int[] t) {  // trier tableau int[] t  ( complexite n^2)
    boolean permut = true;   //témoin de permutations entre éléments dans le tableau 
                             //l'initialise à true de façon à rentrer dans la boucle while
                             
    while (permut) {        // Tant qu'il y a eu au moins une permutation on itère
        permut=false;			
        for(int i=0;i<t.length-1;i++){
            if(t[i]>t[i+1]) {     // Si deux éléments sont mal ordonnés
                swap(t,i,i+1);    // on les échange dans le tableau
                permut=true;      // on se rappelle qu'on a fait (au moins) une permutation
            }
        }
    }
}

Version encore plus simple, toujours $O(N^2)$ dans le pire cas mais un peu moins efficace en pratique (sans témoin de permutation).

public static void triBulle(int[] t) {  // trier tableau int[] t  ( complexite n^2)
    for(int j=0; j<t.length-1;j++){
        for(int i=0;i<=j-1;i++){
            if(t[i]>t[i+1]) {     // Si deux éléments sont mal ordonnés
                swap(t,i,i+1);    // on les échange dans le tableau
            }
        }
    }
}

7. tri **fusion**