1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| #include <stdio.h>
#include <stdlib.h>
#include <time.h> // pour initialiser srand()
/* Cette fonction échange les éléments i et j dans le tableau t */
void echange(int t[], int i, int j)
{
int tmp;
tmp = t[i];
t[i] = t[j];
t[j] = tmp;
}
/* Cette fonction recherche le plus grand élément du tableau t de taille n.
* Elle renvoie l'indice qui correspond à cet élément.
* On suppose que n > 0
*/
int cherche_max(int t[], int n)
{
int i,i_max;
i_max = 0; // le i_max (indice du max) est initialisé à 0, ie le max est supposé être le 1er élément du tableau.
for(i=1;i<n;i++) // on parcourt tous les éléments à partir du 2ième.
{
if( t[i] > t[i_max] ) // Si on a un élément plus grand que le max trouvé pour l'instant...
i_max = i; // ... le nouveau max est l'élément d'indice i, ie l'indice du nouveau max est i.
}
return i_max; // à la fin de la boucle, l'indice du max est dans i_max.
}
/* Le tri par sélection :
* Algo : on va trier le tableau t de taille n en suivant l'algo suivant :
* - on recherche l'indice de l'élément max dans le tableau de taille n ;
* - on échange l'élément max avec le dernier, ainsi il est bien placé ;
* - on recommence avec le meme tableau mais en allant seulement jusqu'à l'élément (n-1).
* - A la fin, quand n vaut 1, le tableau est trié : un tableau à un seul élément est toujours trié.
*/
void tri_selection_rec(int t[], int n)
{
int i_max;
if( n==1 ) // c'est fini
return;
else
{
i_max = cherche_max(t,n); // on recherche l'élément max
echange(t, i_max, n-1 ); // on l'échange avec le dernier
tri_selection_rec(t, n-1); // on recommence avec le tableau sans la dernière case
}
}
/***** Fonctions pour les tests *******/
int alea(int n)
{
return (int) ((double) rand() * (n+1) / ((double)RAND_MAX+1));
}
void gen_tab_aleatoire(int t[], int n)
{
int i;
for(i=0;i<n;i++)
t[i] = i;
for(i=n-1; i>=0; i--)
echange(t,i,alea(i));
}
void print_tab(int t[], int n)
{
int i;
printf("[");
if(n>0)
{
for(i=0;i<n-1;i++)
printf("%d; ",t[i]);
printf("%d",t[n-1]);
}
printf("]\n");
}
/********************************************/
int main(void)
{
int t[20];
srand (time (NULL)); // initialisation du générateur de nombres aléatoires
gen_tab_aleatoire(t,20);
print_tab(t,20);
tri_selection_rec(t,20);
print_tab(t,20);
return 0;
} |
Mon programme se termine prématurément
Répondre avec citation
Envoyé par chicabonux
. D'ailleurs tu l'a toi même appelé recherche, et ça s'en rapproche plus.
Partager