Exercices langage C tri de Shell d'un tableau


Exercice 1


Traduire la fonction TRI_SHELL définie ci-dessous en C. Utiliser la fonction PERMUTER définie dans le cours.

Ecrire un programme profitant des fonctions définies dans les exercices précédents pour tester la fonction TRI_SHELL.

 

   procédure TRI_SHELL(T,N)
| (* Trie un tableau T d'ordre N par la méthode
| de Shell en ordre croissant. *)
| résultat: entier tableau T[100]
| donnée: entier N
| entier SAUT, M, K
| booléen TERMINE
| en SAUT ranger N
| tant que (SAUT>1) faire
| | en SAUT ranger SAUT divent 2
| | répéter
| | | en TERMINE ranger vrai
| | | pour M variant de 1 à N-SAUT faire
| | | | en K ranger M+SAUT
| | | | si (T[M]>T[K]) alors
| | | | | PERMUTER(T[M],T[K])
| | | | | en TERMINE ranger faux
| | | | fsi
| | | fpour
| | jusqu'à TERMINE
| ftant (* SAUT <= 1 *)
fprocédure (* fin TRI_SHELL *)

Remarque: L'algorithme a été développé par D.L.Shell en 1959. En comparant d'abord des éléments très éloignés, l'algorithme a tendance à éliminer rapidement les grandes perturbations dans l'ordre des éléments. La distance entre les éléments qui sont comparés est peu à peu réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.


Exercice 2


Déterminer le maximum de N éléments d'un tableau TAB d'entiers de trois façons différentes:

a) la fonction MAX1 retourne la valeur maximale

b) la fonction MAX2 retourne l'indice de l'élément maximal

c) la fonction MAX3 retourne l'adresse de l'élément maximal

Ecrire un programme pour tester les trois fonctions.


 

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
#include <stdio.h>

main()
{
 /* Prototypes des fonctions appelées */
 void TRI_SHELL(int *T, int N);
 void LIRE_TAB (int *TAB, int *N, int NMAX);
 void ECRIRE_TAB (int *TAB, int N);
 /* Variables locales */
 int T[100]; /* Tableau d'entiers */
 int DIM;    /* Dimension du tableau */ 

 /* Traitements */
 LIRE_TAB (T, &DIM, 100);
 printf("Tableau donné : \n");
 ECRIRE_TAB (T, DIM);
 TRI_SHELL(T, DIM);
  printf("Tableau trié : \n");
 ECRIRE_TAB (T, DIM);
 return 0;
}

void TRI_SHELL(int *T, int N)
{
  /* Trie un tableau T d'ordre N par la méthode de Shell */
 /* Prototypes des fonctions appelées */
 void PERMUTER(int *A, int *B);
 /* Variables locales */
 int SAUT, M, K;
 int TERMINE;
 /* Traitements */
 SAUT = N;
 while (SAUT>1)
     {
      SAUT /= 2;
      do
         {
          TERMINE=1;
          for (M=0; M<N-SAUT; M++)  /* Attention aux indices! */ 
               {
                K=M+SAUT;
                if (*(T+M) > *(T+K))
                   {
                    PERMUTER(T+M,T+K);
                    TERMINE=0;
                   }
               }
         }
      while(!TERMINE); /* Attention: utiliser la négation de */
     }        /* la condition employée en lang algorithmique */
}

void PERMUTER(int *A, int *B)
{
 int AIDE;
 AIDE = *A;
 *A   = *B;
 *B   = AIDE;
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
 . . .
}
void ECRIRE_TAB (int *TAB, int N)
{
 . . .
}

Déterminer le maximum de N éléments d'un tableau TAB d'entiers de trois façons différentes:



 

a) la fonction MAX1 retourne la valeur maximale

 

1
2
3
4
5
6
7
8
9
int MAX1(int *TAB, int N)
{
 int MAX,I;  /* variables d'aide */
 MAX=*TAB;
 for (I=1; I<N; I++)
     if (MAX < *(TAB+I))
         MAX = *(TAB+I);
 return MAX;
}

 

b) la fonction MAX2 retourne l'indice de l'élément maximal
1
2
3
4
5
6
7
8
9
10
11
int MAX2(int *TAB, int N)
{
 int I,MAX; /* variables d'aide */
 MAX=0;
 for (I=1; I<N; I++)
	  if (*(TAB+MAX) < *(TAB+I))
         MAX = I;
 return MAX;
}

 

 

c) la fonction MAX3 retourne l'adresse de l'élément maximal

 

1
2
3
4
5
6
7
8
9
int *MAX3(int *TAB, int N)
{
 int *MAX, *P; /* pointeurs d'aide */
 MAX=TAB;
 for (P=TAB; P<TAB+N; P++)
	  if (*MAX < *P)
         MAX=P;
 return MAX;
}

 

Ecrire un programme pour tester les trois fonctions:

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
#include <stdio.h>

main()
{
 /* Prototypes des fonctions appelées */
 int MAX1 (int *TAB, int N);
 int MAX2 (int *TAB, int N);
 int *MAX3(int *TAB, int N);
 void LIRE_TAB (int *TAB, int *N, int NMAX);
 void ECRIRE_TAB (int *TAB, int N);
 /* Variables locales */
 int T[100]; /* Tableau d'entiers */
 int DIM;    /* Dimension du tableau */ 

 /* Traitements */
 LIRE_TAB (T, &DIM, 100);
 printf("Tableau donné : \n");
 ECRIRE_TAB (T, DIM);
 printf("MAX1 : %d \n",   MAX1(T,DIM)  );
 printf("MAX2 : %d \n", T[MAX2(T,DIM)] );
 printf("MAX3 : %d \n",  *MAX3(T,DIM)  );
 return 0;
}
int MAX1(int *TAB, int N)
{
 . . .
}
int MAX2(int *TAB, int N)
{
 . . .
}
int *MAX3(int *TAB, int N)
{
 . . .
}
void LIRE_TAB (int *TAB, int *N, int NMAX)
{
 . . .
}
void ECRIRE_TAB (int *TAB, int N)
{
 . . .
}

 



 

 

 


Exercice 10.17 Tri de Shell


 

Traduire la fonction TRI_SHELL définie ci-dessous en C. Utiliser la fonction PERMUTER définie dans le cours.

 

Ecrire un programme profitant des fonctions définies dans les exercices précédents pour tester la fonction TRI_SHELL.

 

   procédure TRI_SHELL(T,N)
| (* Trie un tableau T d'ordre N par la méthode
| de Shell en ordre croissant. *)
| résultat: entier tableau T[100]
| donnée: entier N
| entier SAUT, M, K
| booléen TERMINE
| en SAUT ranger N
| tant que (SAUT>1) faire
| | en SAUT ranger SAUT divent 2
| | répéter
| | | en TERMINE ranger vrai
| | | pour M variant de 1 à N-SAUT faire
| | | | en K ranger M+SAUT
| | | | si (T[M]>T[K]) alors
| | | | | PERMUTER(T[M],T[K])
| | | | | en TERMINE ranger faux
| | | | fsi
| | | fpour
| | jusqu'à TERMINE
| ftant (* SAUT <= 1 *)
fprocédure (* fin TRI_SHELL *)

Remarque: L'algorithme a été développé par D.L.Shell en 1959. En comparant d'abord des éléments très éloignés, l'algorithme a tendance à éliminer rapidement les grandes perturbations dans l'ordre des éléments. La distance entre les éléments qui sont comparés est peu à peu réduite jusqu'à 1. A la fin du tri, les éléments voisins sont arrangés.