Bonjour, voila j’essaye de trier un tableau avec le tri par fusion, mais je sais pas pourquoi mon code ne marche pas, alors que tout est en place; voila mon programme:
#include <stdio.h>
#include <stdlib.h>
void fusionner(int tableau[],int debut,int milieu,int fin);
void triFusion(int tableau[],int debut,int fin){
int milieu=0;
if (debut<fin)
{
milieu=(debut+fin)/2;
triFusion(tableau,debut,milieu);
triFusion(tableau,milieu+1,fin);
fusionner(tableau,debut,milieu,fin);
}
}
void fusionner(int tableau[],int debut,int milieu,int fin){
int i,i1,i2;
int tmp[100];
i=1;
i1=debut;
i2=milieu+1;
while((i1<=milieu) && (i2<=fin)){
if(tableau[i1]<tableau[i2]){
tmp[i]=tableau[i1];
i1++;
}
else{
tmp[i]=tableau[i2];
i2++;
}
i++;
}
while(i1<=milieu){
tmp[i]=tableau[i1];
i1++;
i++;
}
while(i2<=fin){
tmp[i]=tableau[i2];
i2++;
i++;
}
for (int j = 0; j < fin; ++j)
{
tableau[j]=tmp[j];
}
}
int main(){
int tableau[100];
int taille=0;
printf("donner la taille: ");
scanf("%d",&taille);
for (int i = 0; i < taille; ++i)
{
printf("tableau[%d]=",i+1);
scanf("%d",&tableau[i]);
}
int debut=1;
int fin=taille;
triFusion(tableau,debut,fin);
for (int i = 0; i < taille; ++i)
{
printf("%d\n",tableau[i]);
}
return 0;
}
Ton code est un peut bizarre, la variable i n'a pas de role a proprement parler, elle compte quelque chose mais on ne sait pas quoi. Ton tableau tmp ne presente auccun avantage
#include <stdio.h>
#include <stdlib.h>
void fusionner(int tableau[],int debut,int milieu,int fin);
void triFusion(int tableau[],int debut,int fin){
int milieu=0;
if (debut<fin)
{
milieu=(debut+fin)/2;
triFusion(tableau,debut,milieu);
triFusion(tableau,milieu+1,fin);
fusionner(tableau,debut,milieu,fin);
}
}
void fusionner(int tableau[],int debut,int milieu,int fin){
int i,i1,i2;
int tmp[100]; // pourquoi tu l'utilise, inutile
i=1;// il ne commence pas a 1 mais au debut du sous tableau
i1=debut;
i2=milieu+1;
while((i1<=milieu) && (i2<=fin)){
if(tableau[i1]<tableau[i2]){
tmp[i]=tableau[i1];
i1++;
}
else{
tmp[i]=tableau[i2];
i2++;
}
i++; // incrementation bonne
}
while(i1<=milieu){
tmp[i]=tableau[i1];
i1++;
i++;
}
while(i2<=fin){
tmp[i]=tableau[i2];
i2++;
i++;
}
for (int j = 0; j < fin; ++j)//cette boucle ne sert a rien en temps normal
{
tableau[j]=tmp[j];
}
}
int main(){
int tableau[100];
int taille=0;
printf("donner la taille: ");
scanf("%d",&taille);
for (int i = 0; i < taille; ++i)
{
printf("tableau[%d]=",i+1);
scanf("%d",&tableau[i]);
}
int debut=1;//le debut d'un tableau en c est 0
int fin=taille;
triFusion(tableau,debut,fin);
for (int i = 0; i < taille; ++i)
{
printf("%d\n",tableau[i]);
}
return 0;
}
Voila un code avec les lines a probleme avec des commentaires
jles fautes d'orthographe sont une seconde nature pour moi
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il y a que la troisième qui marche
Mais avant, ce que tu as fait, c'est fusionner les deux moitiés de la tranche (debut..fin) dans le tableau tmp à partir de l'indice 1 (qui devrait être zero mais peu importe).
Forcément, avec ça, tes données partent un peu dans la nature.
---
En fait il est plus simple, pour noter une "tranche" de tableau, d'avoir l'indice du premier élément et l'indice qui suit le dernier.
void triFusion(int tableau[], int debut, int fin)
{
if (fin - debut > 1) // plus d'un élément à trier
{
int milieu = (debut + fin) / 2;
triFusion(tableau, debut, milieu);
triFusion(tableau, milieu, fin);
fusionner(tableau, debut, milieu, fin);
}
}
void fusionner(int tableau[], int debut, int milieu, int fin)
{
int tmp[100];
int i = debut;
int i1 = debut;
int i2 = milieu;
while ((i1 < milieu) && (i2 < fin))
{
tmp[i++] = (tableau[i1] < tableau[i2])
? tableau[i1++]
: tableau[i2++];
}
while (i1 < milieu)
{
tmp[i++] = tableau[i1++];
}
while (i2 < fin)
{
tmp[i++] = tableau[i2++];
}
for (int j = debut; j < fin; ++j)
{
tableau[j] = tmp[j];
}
}
Appel par
triFusion(tableau, 0, taille); // de 0 à taille-1
- Edité par michelbillaud 18 février 2020 à 17:52:26
Non j'utilise la même plage d'indices pour la partie à trier et la zone de tri. L'indice i commence à début, pas a 0.
Si tu sais faire la fusion sur place, sans tableau supplémentaire, et en temps linéaire, tu devrais le publier, parce que ce n'est pas un problème simple.
Les expressions conditionnelles "ternaires" sont un élément de la boîte à outils. Il n'y a pas à aimer ou pas aimer, il faut juste savoir s'en servir, et savoir quand les employer. Et pour savoir les employer, il faut les voir à l'oeuvre de temps en temps.
- Edité par michelbillaud 18 février 2020 à 22:54:25
7 tmp = tableau[i2]; // Sauver le minimum se trouvant en i2.
8 // Décaler les positionde i1 à i2-1 de 1 vers la droite.
9 for(int k=i2-1; k >= i1; k--) tableau[k+1] = tableau[k];
10 tableau[i1] = tmp; // Placer l'élément venant de i2 en i1.
♠11 i2++; // Élément suivant de la seconde séquence.
12 }
13 i1++; // Nécessaire dans les deux cas.
14 }
15 }
Je ne sais pas si c'est linéaire en N. Les décalages sont moins coûteux que pour le tri par insertion.
Pour réduire le nombre de décalages et le nombre d'éléments décalée au total, il faudrait savoir combien d'éléments à partir de 'i2' peuvent être placés avant 'i1'
Si c'est plus que 1, on se retrouve devant un décalage circulaire.
J'ai déjà traité le sujet et ça risque de devenir assez compliqué. Voici la référence:
Non ce n'est pas linéaire, parce qu'un peu de (mal)chance, il va falloir décaler chaque élément de la moitié du tableau, et ça te donne un algorithme quadratique de fusion, donc dans la catégorie des algorithmes naïfs, comme le tri à bulles par insertion ou par sélection. Et même pire : n² log n.
Google : in place merge sort. Dans https://www.geeksforgeeks.org/in-place-merge-sort/ il y a bien la fusion sur place, mais pas en temps linéaire. Avec la conclusion que c'est en n² log n, donc que c'est pas bon, et il manque d'en tirer les conséquences, qui sont qu'il vaudrait mieux ne pas en parler :-)
Sinon, la fusion sur place linéaire, c'est encore un sujet de recherche chaud (papier de 2008) :
Les recherches que j'ai faites ne m'ont en effet donné aucun résultat sur un tri potentiellement linéaire pour un tri sur place.
Toutes les variantes utilisent un tableau temporaire. La meilleure possibilité est d'utiliser un tableau correspondant à la moitié de l'intervalle.
Je remarque que, si la longueur est impaire, c'est la première moitié qui est la plus longue (un de plus).
L'idée est de copier la première moitié dans le tableau temporaire dès le début et de renvoyer la fusion dans le tableau d'origine.
Si on ne sauve pas de temps, on sauve la moitié de l'espace requis.
Si les fonctions ne savent pas la longueur à trier, il faudra penser à de l'allocation dynamique.
Dans l'exemple, je peux trier jusqu'à 100 éléments, mais je ne peux pas pour plus long.
Je reste dans le contexte où je compile séparément mes fonctions de tri et le main.
J'ai fait de petits test avec l'attribut 'static' et utiliser 'malloc' pour allouer l'espace.
Le seul hic est qu'on ne peut faire qu'un seul tri dans le programme.
Il faudra que je fasse une fonction 'reset' qui libère l'espace à la fin et remette le pointeur à NULL.
Il faudra que ce tableau soit réservé dès le premier appel à triFusion car le premier appel à fusionner ne fusionne que de petits intervalles (2 fois 1 élément)
Ensuite il fusionne des intervalles de plus en plus grands. Je ne veux pas passer mon temps à faire des malloc, realloc ou free.
Comme ça arrive trop souvent, l'auteur n'est pas très bavard, même s'il s'est connecté depuis la création de son post.
Le Tout est souvent plus grand que la somme de ses parties.
Trier un tableau par l'algorithme de fusion
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il y a que la troisième qui marche
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.