# TD4 - DEV5.1 Qualité algorithmique
## Exo 2
### function_1()
pire des cas de parcours nombre1\*nombre2, donc complexité = O(nombre1\*nombre2)

### function_2()
Boucle parcourue jusqua que x = 0 donc il ya a x parcours de la boucle, complexité = O(x)

### function_3()
un seul parcour de la boucle, complexité = O(1)

## Exo 3
### sort_students()
```
void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
{
    int i = 0, j = 0;
    for(i = 0; i < grades_number; i++)
    {
        int * grades = (int*) malloc(students_number*sizeof(int));
	for(j = 0; j < students_number; j++)
	{
	    grades[j] = students_array[j][i];
	}
        bubblesort(grades,students_number);
	for(j = 0; j < students_number; j++)
	{
            students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number);
	}
	free(grades);
    }
}
```
Si l'on suppose que:
- La complexité de “malloc” est O(1)
- La complexité de “free” est O(1)

On commence par calculer les complexité algorythmique des fonctions comprises dans sort_students().

**D'abord la complexité de bublesort() :**
```
void bubblesort(int* array, int length)
{
	int swapped, i, tmp;
	do
	{
		swapped = 0;
		for(i=1;i<length;i++)
		{
			if(array[i-1] > array[i])
			{
				tmp = array[i-1];
				array[i-1] = array[i];
				array[i] = tmp;
				swapped++;
			}
		}
	} while(swapped==1);
}
```
La boucle while continue tant que swapped = 1, or celle si ne l'est que lorsqu'il a parcourue entierement la boucle sans l'avoir modifier.
Dans le meilleur des cas c'est 1 seul parcours, dans le pire c'est n² car il doit reinverser tout le tableau. 
Donc O = n².  


**Ainsi que de find_rank_student():**
```
int <find_rank_student>(int student_grade, int* grades_array, int students_number)
{
    int position = -1;
    int i = 0;
    bubblesort(grades_array,students_number);
    for(i = students_number-1; i >= 0; i--)
    {
        if(grades_array[i] == student_grade)
        {
                position = students_number-i;
            break;
        }
    }
    return position;
}
```
Cette fonction contient bubblesort() qui a une complexité de N². De plus elle contien une boucle for qui s'execute students_number-1 fois. 
Dans le pire des cas cette fonction la boucle fera donc n-1 parcours. La complexité algorythmique est donc de O(n²+(n-1)).


On peut donc enfin calculer la complexité de sort_students():
```
void sort_students(int** students_rank, int** students_array, int students_number, int grades_number)
{
    int i = 0, j = 0;
    for(i = 0; i < grades_number; i++)
    {
        int * grades = (int*) malloc(students_number*sizeof(int));
        for(j = 0; j < students_number; j++)
        {
            grades[j] = students_array[j][i];
        }
        bubblesort(grades,students_number);
        for(j = 0; j < students_number; j++)
        {
            students_rank[j][i] = find_rank_student(students_array[j][i],grades,students_number);
        }
        free(grades);
    }
}
```

Il y a trois boucle dans sort_students, l'une avec un malloc de complexité O(1) qui s'éxecute grades_number fois, un bublesort qui depend de students_number et deux autre boucles qui séxecute students_number fois. La premiere boucle sexecute donc n fois, le bublesort a une complexité de N², la seconde boubcle contient find_rank_student(), elle a donc une complexité de N*(N²+(N-1)) et enfin il y a un free qui vaut donc 1. 
Si l'on calcule cela fait donc = M(1+N+N²+N*(N²+(N-1))+1)
= M(2+N+N²+N3+N²-N)
= M(N3+2N²+2)
On garde la plus complexité la plus elevé donc O(M*N3)

### Exo 4
Mon code se compose en fait de 2 buble sort, la complexité de sort_bubble_array() donc de O(n²), et celle de bublesort_multi_array() est de O(n²+n²) donc O(n²)