comment insere un élément dans un tab trié ?

j'ai une question : j'ai un tableau de dimension n+1
contient n valeurs triés par ordre croissant
la (n+1) ème valeur est indéfinie
je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !
c'est à dire je vais comparer ( x ) et les autres éléments du tabelau jusqu'a trouver la dernière valeur ( a ) qui précéde ( x ) dans le tableau ( cad x>a et puis x< a+1 )
Apres je doit décaler les éléments qui suit (x) pour que je puisse l'insérer, et donc j'ai rempli la (n+1)ème valeur du tableau
question : comment on peu décaler ce tableau ?

voila un exemple :
le tableau est de 6 cases ( tableau trié par ordre croissant, le dernier élément est pas définie )

----------------------------
1 | 2 | 3 | 5 | 6 | indéfine |
----------------------------

je doit insérer x=4 dans ce tableau
je doit faire le parcours " tantque ( x>t[i] ) ..."
je m'arrete à la case conteannt la valeur 5
je doit insérer x=4 dans la case entre 3 et 5
pour ca je doit décaler la partie " 5|6 " du tableau à droite pour libérer une case de x, et comme ca on a rempli tout le tableau
comment peu on décaler ce tableau & insérer la valeur 4 ?
( merci pour votre aide )

Citation:

---

Envoyé par sablito

j'ai une question : <...>

---

Par copie des éléments. Avec un tableau, il n'y a pas d'autre solution.

Un peu de méthodologie. Pour résoudre un problème quel qu'il soit, il faut passer au moins par 3 étapes dans l'ordre :

1 - Définition : quoi ?
2 - Conception : comment ?
3 - Réalisation (ici, codage et tests)

La définition est ici l'énoncé du problème. Il est assez clair :

Citation:

---

j'ai un tableau de dimension n+1
contient n valeurs triés par ordre croissant
la (n+1) ème valeur est indéfinie
je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !

---

Ensuite, il y a une tentative de résolution du problème que l'on peut assimiler à de la conception :

Citation:

---

c'est à dire je vais comparer ( x ) et les autres éléments du tabelau jusqu'a trouver la dernière valeur ( a ) qui précéde ( x ) dans le tableau ( cad x>a et puis x< a+1 )
Apres je doit décaler les éléments qui suit (x) pour que je puisse l'insérer, et donc j'ai rempli la (n+1)ème valeur du tableau
question : comment on peu décaler ce tableau ?

---

et finalement une question dont la réponse a déjà quasiment été donnée dans l'analyse précédente. Il suffit maintenant de décrire le comportement avec de phrases simples et claires. Par exemple, ceci en 'premier jet'.

• Faire une copie de l'élément à insérer
• Parcourir le tableau pour trouver sa position d'insertion
• Noter la position
• Aller en fin de tableau
• De la fin du tableau à la position d'insertion, copier chaque élément à la position suivante
• Copier l'élément à insérer

Maintenant, on peut réfléchir à une meilleure séquence qui aurait pour effet de réduire les déplacements :

• Aller à la position de l'élément à insérer (par définition la fin de tableau)
• Faire une copie de l'élément à insérer
• De la fin du tableau à la position d'insertion, copier chaque élément à la position suivante
• Copier l'élément à insérer

et voilà, tout simplement.

Ce travail de reflexion est essentiel. C'est ici que se fait la conception, et les choix déterminants la performance. Et c'est pour ça qu'on est payé ! Le codage, c'est secondaire. Une machine un peu douée sachant lire le texte précédant saurant en tirer du code et les jeux de tests correspondants un jour ou l'autre...

Citation:

---

Envoyé par markipoli

Je suis dans la même situation mais je bloque depuis plusieurs jours pour un projet que je dois rendre après demain :-/ je désespère. Si vous pouviez <...>

---

Il est parfaitement impoli et déplacé de squatter la discussion d'un autre. C'est à toi de créer ta discussion si tu veux qu'elle soit suivie.

Question supprimée.

Salut,

Merci, je ne m'attendais pas à un tel rappel à l'ordre alors que sur tout les forums que j'ai vu de ma vie on préfère réutiliser les topics déjà existants plutôt que d'en faire un autre à propos du même soucis...

Je ne savais pas que c'était « parfaitement impoli et déplacé » et je n'assimilais pas cela à du squatte. Désolé, je ne referai plus la même erreur, et j'apprendrai à sauvegarder une copie des messages que je posterai de peur qu'ils soient de nouveau supprimés sans préavis, et donc de reperdre un temps fou à retaper parfaitement et clairement mon message, du fait de mon ignorance des règles exotiques et implicites telles que celle ci (et qui n'est même pas dans la charte : http://club.developpez.com/regles/).

Encore désolé :-/

PS : sans remettre en cause la modération, j'apporte juste un précision, après les modérateurs font ce qu'ils veulent...

@++

Citation:

---

Envoyé par sablito

j'ai une question : j'ai un tableau de dimension n+1
contient n valeurs triés par ordre croissant
la (n+1) ème valeur est indéfinie
je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !

---

Code:

---

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

#include <stdio.h> #include <stdlib.h>   void printinttab(int* tab, int taille){ int i; for(i = 0; i < taille; i++){ printf("%d - %d\n", i, tab[i]); } }   int compareint(const void* a, const void* b){ return *(int*)a - *(int*)b; }     int main(void) { #define PETRUS_TAILLE (sizeof rats / sizeof(int)) int rats[] = {1, 2, 3, 5, 6, 0}; rats[PETRUS_TAILLE - 1] = 4; puts("rats pas triés:"); printinttab(rats, PETRUS_TAILLE); qsort(rats, PETRUS_TAILLE, sizeof(int), compareint); puts("rats triés:"); printinttab(rats, PETRUS_TAILLE); #undef PETRUS_TAILLE return EXIT_SUCCESS; }

---

Mais c'est pas sûr que ce soit ce que souhaite le prof ...

Citation:

---

Envoyé par Pierre Maurette

Code:

---

1 2 3 4 5 6 7 8

... qsort(rats, PETRUS_TAILLE, sizeof(int), compareint); puts("rats triés:"); printinttab(rats, PETRUS_TAILLE); #undef PETRUS_TAILLE return EXIT_SUCCESS; }

---

Mais c'est pas sûr que ce soit ce que souhaite le prof ...

---

Absolument. Le topic parle de méthode d'insertion dans un tableau déjà trié et non d'insertion puis de tri à l'issue. A la limite la solution demandée doit fonctionner même si la fonction qsort() n'existe pas...