Programme de tri en C

par **Kimou** » 01 Oct 2009, 20:34

Bonjour je ne sais absolument RIEN de C et j'aurai voulu réaliser un programme, histoire de m'exercer en tri pour cette année...
--------------------------------------------------------------------------
EXERCICE:
On veut trier un tableau qui ne contient que des 0 et des 1. Proposer un algorithme qui n'effectuerait qu'un nombre linéaire d'opérations (en fonction de la taille du tableau)
--------------------------------------------------------------------------
"Pseudo-code":
Je pensais en fait parcourir une fois le tableau en comptant d'une part la taille du tableau et d'autre part en stockant le nombre de 1 qu'il y a.
Puis faire un deuxième passage en remplacant de [du début du tableau ; à (la taille du tableau - le nombre de 1)] les 1 en 0 puis de [(la taille du tableau - le nombre de 1) à la fin tu tableau] en remplacant les 0 en 1.
Est ce bon?
Comment l'écrire en C? y a il beaucoup de différence avec le langage java?
Merci par avance!

par **Dominique Lefebvre** » 01 Oct 2009, 20:38

Bonsoir,

Sans présumer de la qualité de ton algo, je te dirais que si tu n'essayes pas de créer une classe en C, pondre un algo de ce genre en java ou en C; c'est du pareil au même.. Tu vas utiliser des boucles et des conditions..; maintenant, il ya qq différences que tu ne saisiras que lorsque tu auras appris le C!

par **Kimou** » 01 Oct 2009, 20:41

Dominique Lefebvre a écrit:Bonsoir,

Sans présumer de la qualité de ton algo, je te dirais que si tu n'essayes pas de créer une classe en C, pondre un algo de ce genre en java ou en C; c'est du pareil au même.. Tu vas utiliser des boucles et des conditions..; maintenant, il ya qq différences que tu ne saisiras que lorsque tu auras appris le C!

Bonsoir,
oui je ne suis pas en informatique et j'ai juste fait du java (à petite echelle), donc d'après ce que tu dis il ne devrait pas avoir trop de différence. Je vais essayer d'écrire en java et si vous pouviez jeter un coup d'oeil ca serait sympa

edit: apres réfléxion en fait je ne peux pas compter la taille du tableau sans savoir le parcourir? car la boucle doit etre défini non?

par **Dominique Lefebvre** » 01 Oct 2009, 20:55

Kimou a écrit:Bonsoir,
edit: apres réfléxion en fait je ne peux pas compter la taille du tableau sans savoir le parcourir? car la boucle doit etre défini non?

De toute manière, pour coder ton source, tu seras obligé d'assigner une taille à ton tableau, que tu utilises une allocation statique ou dynamique de la mémoire...

par **Kimou** » 01 Oct 2009, 20:59

Dominique Lefebvre a écrit:De toute manière, pour coder ton source, tu seras obligé d'assigner une taille à ton tableau, que tu utilises une allocation statique ou dynamique de la mémoire...

Désolé mais je ne comprend pas trop la fin de phrase je n'ai pas encore vu cela.
Mais l'exercice demande de trier un tableau dont on ne connais pas la taille au départ avec un nombre de 1 et 0 aléatoirement et de quantité non définie... c'est ça que tu dois mettre sous le terme mémoire dynamique je pense?

par **Dominique Lefebvre** » 01 Oct 2009, 21:11

Kimou a écrit:Désolé mais je ne comprend pas trop la fin de phrase je n'ai pas encore vu cela.
Mais l'exercice demande de trier un tableau dont on ne connais pas la taille au départ avec un nombre de 1 et 0 aléatoirement et de quantité non définie... c'est ça que tu dois mettre sous le terme mémoire dynamique je pense?

Tu ne peux pas coder ce genre d'exercice tel quel! Ton compilateur exige que tu assignes une taille à ton tableau. l'allocation statique ou dynamique est un point technique sans importance ici.
Ton exo me rappelle une méthode de tri qui s'appelle le tri par comptage d'occurence... C'est d'ailleurs la voie que tu sembles avoir choisi. Je ne sais plus s'il est linéaire, je crois que oui. Mais de toute manière, tu seras amené à borner ton tableau, soit en indiquant sa taille désignée par un paramètre (N par tradition) ou en marquant sa fin par un caractère quelconque. Sinon, tu vas te retrouver avec une boucle infinie, peu appréciée :-)

)

par **fatal_error** » 02 Oct 2009, 12:10

salut,

dans ton cas,
tu fais un parcours de tableau : n
puis dans tu reparcours le tableau (en decomposant certes en deux boucles) : n

L'ordre est de O(2n)=O(n)

Un autre moyen est simplement de recopier le tableau dans un autre.
Dans ton tableau de ref, des que tu trouves un 0, tu lajoutes a la fin de ton tableau de copie.
Une fois que tu as parcouru ton tableau de reference, il te reste plus qu'a compléter ton tableau de copie avec des 1.

par **Kimou** » 04 Oct 2009, 16:41

la fonction malloc ne pourrait pas nous aider ici?
J'ai tenter de regarder des algo de tri sur des forums mais j'avoue que je ne comprend pas (moins explicite que du java)...
Vous pouvez m'aider?
PS: comment puis je faire du C sur windows?

par **fatal_error** » 04 Oct 2009, 18:37

re,

il y a un wagon de tutos sur le net.
Le site du zero, et plein d'autres.

un malloc ne sert a rien dans notre cas car :
un malloc sert a allouer dynamiquement de la mémoire.
C'est a dire que lorsque tu compiles ton programme, tu sais pas combien de taille va faire ton tableau.
Dans ce cas, tu fais un malloc. Du coup, une fois que le prog est executé, si tu as besoin davoir 3 cases supplémentaires, tu fais (grossièrement) un malloc(3) ce qui te permet davoir trois cases supplémentaires. Idem avec n cases.

Néanmoins, si tu connais la taille du tableau avant lexecution du programme, il est tout a fait inutile de faire un malloc.
il te suffit de declarer par exemple
int t[123]; //ton tableau de 123 entiers

Dans notre cas, on a pas besoin de cases supplémentaires (rien a insérer dans un tableau).
si le tableau rempli de 1 et de 0 fait 10 cases, ben tu sais que la taille c'est 10. Si eventuellement tu as besoin d'un autre tableau tu sais qu'il faut au moins lui mettre 10 cases. Tu peux donc fixer la taille du tableau AVANT la compilation. no malloc.

par **fatal_error** » 04 Oct 2009, 18:41

Concernant le C sous windo(ws|be), tu peux installer devC++ ou code blocks qui sont des IDE. Il y en a dautres.
Eventuellement, tu peux avoir besoin d'installer un compilateur, mais je crois que c'est fait d'office avec devC++ (je me souviens pas avoir galéré, mais ca remonte...).

PS : un ide c'est (encore une fois grossièrement) un logiciel pour programmer avec du confort.

par **Kimou** » 04 Oct 2009, 19:48

fatal_error a écrit:Concernant le C sous windo(ws|be), tu peux installer devC++ ou code blocks qui sont des IDE. Il y en a dautres.
Eventuellement, tu peux avoir besoin d'installer un compilateur, mais je crois que c'est fait d'office avec devC++ (je me souviens pas avoir galéré, mais ca remonte...).

PS : un ide c'est (encore une fois grossièrement) un logiciel pour programmer avec du confort.

Merci beaucoup pour toutes tes explications j'ai installé code block et ca marche super bien!
Concernant le malloc je ne suis pas d'accord, selon l'énoncé de l'exercice la taille du tableau contenant les 0 et 1 n'est pas défini, d'où aussi al difficulté que je rencontre...
Je comprends qu'il existe un tableau qu'il faut trier, cependant je ne connais pas la taille du tableau. Ce n'est pas ça l'énoncé ?

par **fatal_error** » 04 Oct 2009, 20:35

ben :
Pour trier un tableau, il faut que celui-ci existe.
Deux cas :
soit il existe avant la compilation auquel cas, pas besoin de malloc.

Code: Tout sélectionner: int main() { int t[10]; //compilé }

Soit il existe pas avant.

Code: Tout sélectionner: int main() { cout>taille; //recupere la valeur rentrée. (ecrase 0) int *t=malloc(sizeof(int)*taille); //on reserve de la memoire pour 10 int }

Moyennant les erreurs de syntaxes.

Dans ton exo, il faut certainement découper l'énoncé en deux :
creer le tableau ( et le remplir :-p! )
le trier par la suite

par **Kimou** » 04 Oct 2009, 20:48

héhé d'accord!
Depuis tout à l'heure j'ai tenté de faire des truc, ca n'a pas l'air de marcher pour autant, il compile mais met une erreur par la suite.
J'ai fais une partie "main" avec avec un tableau définie de longueur 4, et une parti fonction "tri" pour faire ce qui m'est demandé.
Je copie ce que j'ai fais (et recopier par ci par là):

Code: Tout sélectionner: int main() { int t[4], i=0; t[0] = 1; t[1] = 0; t[2] = 0; t[3] = 1; for (i = 0 ; i < 4 ; i++) { printf("%d\n", t[i]); } tri(t[4],1); return 0; } int tri(int t[],int n) { int i=-1,j=0,k=n,elt; while (j<k) {if (t[j]==0) {i=i+1; elt=t[i]; t[j]=t[i]; t[i]=elt; j++; } else if (t[j]==1) j++; else {k=k-1; elt=t[k]; t[k]=t[j]; t[j]=elt;} } printf("%d\n", t[i]); }

En fait le "int n" je ne comprend pas vraiment à quoi il sert dans l'appel de la fonction...merci

par **fatal_error** » 04 Oct 2009, 20:53

re,

je t'avouerai franchement : ce code il est moche.
Perds pas de temps a essayer de comprendre un truc aussi moche.

Essaie plutot de voir comment toi tu ferais la chose, et pose des questions sur ce que tu ne comprends pas dans ce que tu as fait.

PS : l'indentation est super importante. Les commentaires aussi.
Si tu codes, indentation et commentaire : pri mordial ! C'est en parti pour ces raisons que le code ci dessus est aussi .. :beurk:

Cela dit, le n c'est probablement la taille du tableau. (pour pas acceder a une case mémoire qui nappartient pas au tableau :D)

par **Kimou** » 04 Oct 2009, 20:57

re,
Oui désolé pour la mocheté mais étant vraiment novice en programmation c'est pas mon fort^^
Quoi qu'il en soit je voulais seulement tester la partie "tri" à proprement parlé:

Code: Tout sélectionner: int tri(int t[],int n) { int i=-1,j=0,k=n,elt; while (j<k) {if (t[j]==0) {i=i+1; elt=t[i]; t[j]=t[i]; t[i]=elt; j++; } else if (t[j]==1) j++; else {k=k-1; elt=t[k]; t[k]=t[j]; t[j]=elt;} } printf("%d\n", t[i]); }

Tu penses pouvoir le tester voir si il marche? ou me donner une partie main valable?^^

par **fatal_error** » 04 Oct 2009, 21:11

désolé, j'aime pas trop débugger.
ps : ca tapporteras rien de copier du code. (du moins pas pour l'instant)

par **Jiss** » 29 Oct 2009, 02:19

fatal_error a l'air de pas mal s'y connaître en C, (sauf que le cout c'est en C++ il me semble :p)

Si jamais vous avez besoin d'aide, je pourrai ptetre vous aider :p

Par contre si tu ne connais pas taille du tableau avant c'est assez embêtant... Tu comptes lui fournir comment le tableau à ton programme ? L'utilisateur entrera à l'écran son tableau, ou alors il sera dans un fichier ? (c'est important de savoir ça)

Programme de tri en C

Programme de tri en C

Qui est en ligne