Tri par insertion/help langage C

Fermé

xvcs - 8 nov. 2010 à 17:30
sabi - 29 mars 2016 à 23:03

Bonjour,

je suis débutante et doit effectuer un petit programme qui va trier un tableau. Or ma fonction tri ne fonctionne pas j'aimerai dans un premier temps que quelqu'un me corrige et mexplique mes erreurs. dans un second temps jaimerai savoir si je reponds bien a la question. voici l'enoncé: donner l'algorithme de la fonction permettant d'inserer a sa place la (i+1)eme valeur t[i] dans les (i+1)ere positions du tableau t supposé trié entre O et i-1: par comparaisons et permutations la valeur inserée remonte dans le tableau jusqu'a sa place.

dans l'attente de vos reponses, merci.

#include <stdio.h>
#include <stdlib.h>
#define max 11
typedef int Tab[max];

void perm(int *a, int *b)
{
int c=*a;*a=*b;*b=c;
}

void inserer1(Tab t, int n)
{
int i,j,a;
for(i=1;i<=n-1;i++)
{
j=i-1;
while((j>=0) && (t[j]>t[j+1]))
{
//a=t[j];
//t[j]=t[j+1];
//t[j+1]=a;
perm(&t[j],&t[j+1]);
j=j-1;
}
}

}

int main()
{
Tab t={0,2,4,6,8,10,14,16,20,18};
int n,i;
for(i=0;i<max;i++)
{
printf("%d\n",t[i]);
}
inserer1(t,11);
printf("Hello world!\n");
return 0;
}

A voir également:

Tri par insertion en c
Excel trier par ordre croissant chiffre - Guide
Insertion sommaire word - Guide
Logiciel tri photo - Guide
Insertion liste déroulante excel - Guide
Touche insertion clavier - Guide

7 réponses

Réponse 1 / 7

xvcs
8 nov. 2010 à 22:10

@Arya Dröttningu: merci davoir repondu.
mais alors c'est quoi le but de la question si on ne me demande pas de trier le tableau?^^ il est question de "tri a insertion" non?
j'ai rebossé le code par rapport a ce que j'ai donc compris!^^

#include<stdio.h>
#include <stdlib.h>
#define n 5
typedef int Tab[n];

/* tri par insertion */
void tri_insertion(Tab t,int i)
{
int j,a;
for(i=1;i<n;i++)
{j=i-1;
while((j>=0) && (t[j]>t[j+1]))
{
a=t[j];
t[j]=t[j+1];
t[j+1]=a;
j--;
}

}
}

/*tri par insertion sequentielle*/
int tri_insertion_seq(Tab t,int i)
{
i
}

int tri_insertion_recursif(Tab t,int i,int k)
{
}

/* affiche le tableau */
void affiche (Tab t, int i)
{
for (i=0;i<n;i++)
printf ("%d ",t[i]);
printf ("\n");
}

int main ()
{
Tab t; int choix, i,r;
for (i=0;i<n;i++)
{
printf("Entrez l'élément %d : ",i+1);
scanf("%d",&t[i]);
}
printf("\ntableau initial : ");
affiche(t,i);
while(choix!=4)
{
printf ("\n********** MENU **********\n");
printf ("1. tri insertion\n");
printf ("2. tri insertion sequentiel\n");
printf ("3. tri insertion recursif\n");
printf("4. quitter");
printf ("\nChoisissez une option : ");
scanf ("%d",&choix);
printf("\n");
switch (choix)
{
case 1:
printf ("Tri insertion: ");
tri_insertion(t,i);
affiche (t,i);
break;
case 2:
printf ("Tri insertion sequentiel: ");
tri_insertion_seq(t,i);
affiche(t,i);
break;
case 3:
printf("Tri insertion recursif: ");
r=tri_insertion_recursif(t,i);
break;
case 4:
printf ("Au revoir!\n");
break;
}
}
return 0;
}

merci d'y preter attention.
alors, d'apres toi, enfaite a la base je suis censé avoir un tableau deja trié, puis rajouter une valeur que je doit placer dans le tableau tout en le gardant trié?? elles sont beaucoup trop complexe leurs questions làà!^^

xvcs
8 nov. 2010 à 22:16

oh mon dieu tant de boulot pour rien si je ne réponds pas a la question!!!! =s
je suis perdu, comment dois-je faire alors?? :/

Réponse 3 / 7

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
9 nov. 2010 à 08:26

J'ai bien relu ta consigne et, selon moi, oui tu dois avoir un tableau déjà trié.
En fait d'après ce que j'ai compris le programme doit juste insérer la valeur, par exemple :
t=[1;3;4] (tableau de départ)
on veut insérer 2, on le met à la fin : t=[1;3;4;2]
on compare 2 et 4 : 2<4 donc on permute : t=[1;3;2;4]
de même pour 2 et 3 : 2<3 donc t=[1;2;3;4]
on compare 2 et 1 là 2>1 donc la valeur est bien placée, fin du programme

Voilà ce que j'ai compris de la consigne

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
Modifié par Arya Dröttningu le 9/11/2010 à 08:44

Pour les fonctions de tri, tu n'as besoin que du tableau en paramètre, idem pour la fonction d'affichage.
Exemple :

void tri_insertion(Tab t)
{
	int i,j,a;
	for(i=1;i<n;i++)
	{
		j=i-1;
		while((j>=0) && (t[j]>t[j+1]))
		{
			a=t[j];
			t[j]=t[j+1];
			t[j+1]=a;
			j--;
		}
	}
}

void affiche (Tab t)
{
	int i ;
	for (i=0;i<n;i++)
		printf ("%d ",t[i]);
	printf ("\n");
}

Réponse 5 / 7

tak21
8 nov. 2010 à 19:55

salut sava????
SVP j'ai besoin de vos aides.. chui débutante...
je doit faire l'algorithme:
soit t un tableau d'entiers.On suppose que ce tableau t n'est pas trié.
Ecrire un algorithme, qui retourne l'élément qui apparait le plus souvent dans le tableau t, ainsi que son nombre d'occurences. Si plusieurs éléments différents répondent au probléme, votre algorithme doit en fournir un, quel qu'il soit. Vous ne devez utiliser aucaun tableau que celui sur lequel vous travaillez.
merci d'avance

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
8 nov. 2010 à 19:57

pas la peine de poster ton sujet dans tous les post !

Réponse 7 / 7

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
9 nov. 2010 à 19:01

Ok si jamais ce n'est pas ça et qu'il fallait faire le tri : désolé ! Mais le plus sûr est effectivement de demander à ton prof.
En tout cas si tu as d'autres problèmes n'hésite pas à revenir ;)

xvcs
11 nov. 2010 à 14:42

Alors bonjour me revoilà!^^ j'hésite pas! ;p
donc j'ai réussi a faire un bon programme qui répond bien a la question d'après mon prof. Et il ma dit que si c'était possible, faire de ma fonction "tri", une fonction recursive. Or j'ai pas encore eu le declic qui me fait comprendre cette methode malheureusement. je sais que la fonction doit "s'auto-appelée"^^ que j'ai besoin d'une condition d'arret, mais quand je tente toute sorte de truc,ça ne me donne jamais le resultat que j'attend... huhu.
je te montre mon code:

#include<stdio.h>
#include <stdlib.h>
#define n 5
typedef int Tab[n];

void affiche (Tab t);

/* tri par insertion */
void tri_insertion(Tab t,int l)
{
int j,a,b,i;
t[n-1]=l;
affiche(t);
for(i=1;i<n;i++)
{j=i-1;
while((j>=0) && (t[j]>t[j+1]))
{
a=t[j];
t[j]=t[j+1];
t[j+1]=a;
j--;
affiche(t);
}
}
}

/*tri par insertion sequentielle*/
void tri_insertion_seq(Tab t,int l)
{
int j,i;
t[n-1]=l;
affiche(t);
j=n-1;
while(j>0 && t[j-1]>l)
{
t[j] = t[j-1];
j--;
affiche(t);
}
t[j]=l;
affiche(t);
}

/* tri par insertion_recursif*/
int tri_insertion_recursif(Tab t, int l)
{int j,a,i;
t[n-1]=l;
affiche(t);
for(i=1;i<n;i++)
{
if(i>n)
j=i-1;
while((j>=0) && (t[j]>t[j+1]))
{
tri_insertion_recursif(t,l-1);
j--;
affiche(t);
}
}
return t;
}

/* affiche le tableau */
void affiche (Tab t)
{
int i;
for (i=0;i<n;i++)
printf ("%d ",t[i]);
printf ("\n");
}

int main ()
{
Tab t={0,2,3,4}, t1={0,2,3,4},t2={0,2,3,4},t3={0,2,3,4} ; int choix,r;
//for (i=0;i<n;i++)
// {
//printf("Entrez l'élément %d : ",i+1);
//scanf("%d",&t[i]);
// }
printf("\ntableau initial : ");
affiche(t);
while(choix!=4)
{
printf ("\n********** MENU **********\n");
printf ("1. tri insertion\n");
printf ("2. tri insertion sequentiel\n");
printf ("3. tri insertion recursif\n");
printf("4. quitter");
printf ("\nChoisissez une option : ");
scanf ("%d",&choix);
printf("\n");
switch (choix)
{
case 1:
printf ("Tri insertion: \n");
tri_insertion(t,1);
printf("Tableau final: ");
affiche(t);
break;

case 2:
printf ("Tri insertion sequentiel: \n");
tri_insertion_seq(t1,1);
printf("Tableau final: ");
affiche(t);
break;

case 3:
printf("Tri insertion recursif: ");
r=tri_insertion_recursif(t2,1);
printf("Tableau final: ",r);
affiche(t);
break;

case 4:
printf ("Au revoir!\n");
break;
}
}
return 0;
}

je sais que mon tri recursif est faux mais je n'ai aucune idée de comment le faire..
pi apres ça je doit faire une "insertion dichotomique" mais c'est une autre histoire je verrai ça plutard. peut-tu m'eclairer sur l'insertion recursive?
je te remercie de "t'occuper" de moi!^^ c'est gentil de depenser ton temps dans mes soucis. ;)

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
11 nov. 2010 à 17:23

Re, désolé je n'étais pas là.....
Bon je me suis pas encore penché sur le code récursif mais ton programme ne peut pas fonctionner :
dans ta fonction récursive tu fais un return t alors que tu as déclarer que le retour était un int

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
11 nov. 2010 à 17:53

Il y a un truc que je ne comprends pas du tout :
dans ta fonction tri_insertion par exemple tu mets deux paramètres..... J'ai exécuté et en fait tu ne fais pas QUE trier ! Tu ajoutes en même temps la valeur 1 : POURQUOI ?

xvcs
11 nov. 2010 à 19:33

bah en gros, mon tableau est trié sauf la derniere valeur, qui doit trouver sa place grace au tri par insertion, donc la valeur qui doit trouver sa place c'est le 1 que je met à la dernière place du tableau. j'ai donc le tableau initial {0,2,3,4} et en appelant mes fonctions, j'envoie le chiffre 1 qui se place a la fin du tableau donc çà me donne {0,2,3,4,1} et la fonction tri me place le 1 a sa place donc ça me donne le tableau final {0,1,2,3,4} . donc ma fonction tri a deux paramètres, le premier, c'est le tableau, et le deuxieme c'est la valeur (donc 1) que je souhaite placer.

et oui par ma récursion je sais bien que c'est totalement faux. c'est pour çà que j'aimerai avoir des explications. mais mon tableau un composé d'entiers.. c'est pour ça que j'ai declaré que le retour etait "int".

Arya Dröttningu Messages postés 581 Date d'inscription mardi 12 janvier 2010 Statut Membre Dernière intervention 3 janvier 2019 157
11 nov. 2010 à 19:37

donc ce n'est pas une fonction de tri que tu as fait mais simplement une fonction qui insère un nombre à sa place dans un tableau trié, non ?

alors si tu mets int maFonction () il faut que tu retourne UN SEUL entier (dans le cas de ta fonction tu ne peux pas retourner le tableau qui contient plusieurs int)

Discussions similaires

tri insertion d'une structure en C

Tri à bulle (langage C)

tri par comptage (decroissant)

tri en programmation C

[Excel] Inserer ligne en gardant les formules

Excel macro insertion de ligne