Exercice langage C: Insertion dans un tableau

Dans cet exercice vous allez apprendre à insérer une nouvelle valeur au bon endroit dans un tableau trié.

Le programme ci-dessous crée un tableau d'entier triés par ordre croissant. Seuls nb_element-1 éléments sont insérés dans le tableau (la derniière case vaut $0$), de telle manière qu'il reste une place de libre pour un nouvel élement.

Copiez le programme dans Emacs et remplacez les points de suspension par du code demandant à l'utilisateur d'entrer un nombre à insérer dans le tableau. Le programme devra ensuite insérer le nombre dans le tableau, de manière à ce qu'il soit toujours correctement trié par ordre croissant.

Finalement, votre programme devra afficher à l'écran le tableau avec le nouvel élément.

Indice: commencez par identifier la place du nouvel élément dans le tableau, puis déplacez les éléments à sa droite d'une case vers la droite, afin de libérer une position.

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
#include 
      #include 

      using namespace std;

      int main(int argc, char **argv) {
        const int nb_elements = 15;
        int tableau[nb_elements];

        srand(time(0));
        tableau[0] = rand() % 50;

        for (int i=1; i<nb_elements-1; i++)
          tableau[i] = tableau[i-1] + (rand() % 20);
        tableau[nb_elements-1] = 0;

        cout << "Tableau initial:" << endl;
        for (int i=0; i<nb_elements; i++)
          cout << tableau[i] << " ";
        cout << endl;

        ...

        return 0;
      }

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
#include 
#include 

using namespace std;

int main(int argc, char **argv) {
  const int nb_elements = 15;
  int tableau[nb_elements];
  int n, pos;

  srand(time(0));
  tableau[0] = rand() % 50;

  for (int i=1; i<nb_elements-1; i++)
    tableau[i] = tableau[i-1] + (rand() % 20);
  tableau[nb_elements-1] = 0;

  cout << "Tableau initial:" << endl;
  for (int i=0; i<nb_elements; i++)
    cout << tableau[i] << " ";
  cout << endl;

  cout << "Entrez un entier a inserer dans le tableau: ";
  cin >> n;

  /* calcul de la position a laquelle on va 
   * inserer le nouvel element */
  pos = 0;  
  while (tableau[pos] < n)
    pos++;

  // decalage des elements vers la droite
  for (int i=nb_elements-1; i>pos; i--)
    tableau[i] = tableau[i-1];

  // insertion du nouvel element
  tableau[pos] = n;

  cout << endl << "Tableau avec le nouvel element:" << endl;
  for (int i=0; i<nb_elements; i++)
    cout << tableau[i] << " ";
  cout << endl;

  return 0;
}