Discussion :

[aaronlbk]

Salut à tous,
je viens vous soumettre mon code mergesort qui ne fonctionne pas,
Je vous présente les fonctions que j'ai écrites :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
46
47
48
49
50
51
52
void fusion(int tab[], int deb, int mid, int end)
{
	int i= deb;
	int j = mid + 1;
	int size = end-deb+1;
	int *tab2= new int[size];
	int k = deb;
	for (int p=0;p<size;p++)
	{
		tab2[p]=tab[p];
	}
 
	while (i<=mid && j <=end )
	{
		if(tab2[i]>tab2[j])
		{
			tab[k]=tab2[j];
			j++;
		}
		else
		{
			tab[k]=tab2[i];
			i++;
		}
		k++;
	}
	while(i<mid)
	{
		tab[k]=tab2[i];
		i++;
		k++;
	}
 
	while(j<end)
	{
		tab[k]=tab2[j];
		j++;
		k++;
	}
 
}
void merge_sort(int tab[], int deb, int end)
{
	if(deb < end)
	{
	int mid=deb+(end-deb)/2;
	merge_sort (tab,deb,mid);
	merge_sort(tab,mid+1,end);
	fusion(tab,deb,mid,end);
	}
 
}

la fonction merge_sort effectue la division progressive du tableau et la fonction fusion fusionne tout en faisant le tri
Pour l'entrée suivante:

|1005|2342|2608|7529|17926|24824|29165|32350|
j'obtiens la sortie qui suit :
|-357437318|-33686019|-33686019|0|1005|2342|7529|32350|

merci d'avance pour votre aide et remarques

[ternel]

Bonjour,

Première remarque, tu as un new, et aucun delete.
C'est grave, tu devrais le remplacer par std::vector<int>(size).

Pour ton problème de valeurs,
Tes valeurs ressemble à des dépassements de valeur, surtout avec 32350, qui est très proche de 32768, qui peut être la frontière des entiers 16 bits signés. Cela dit, vu les valeurs obtenues, je n'y crois pas.
Par acquis de conscience, regarde le comportement pour {100,234,260,752,1792,2482,2916,3235}.

Mon avis, c'est surtout que tu lis du rien, à cause des tableaux et pointeurs.
Du coup, tu conserves de la mémoire aléatoire.

Les valeurs obtenues sont-elles toujours les mêmes d'une exécution à l'autre.

[aaronlbk]

Bonjour ,
J'ai testé avec des valeurs aléatoires entre 0 et 100 et j'obtiens la même chose

[ternel]

Juste pour qu'on voit le problème un peu plus dans son ensemble, tu peux nous donner un main reproduisant ton problème?
Prends {10,135,35,25,350} comme tableau d'exemple.

Car quand le résultat n'est pas bon, ça vient soit du calcul, soit des données (soit des subtilités, comme le passage d'argument).

[aaronlbk]

Voici le main et la fonction d'affichage du tableau en sortie

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void AfficheTableau(int tableau[], int n)
{
	printf("|");
	for(int i = 0; i < n; i++)
	{
		printf ("%d|",tableau[i]);
	}
	printf("\n");
 
}
 
void main()
{
    int test[]={10,135,35,25,350};
    merge_sort( test, 0,4);
    AfficheTableau(test,5);
 
}

Voici le résultat obtenu en sortie:
|0|10|35|35|350|

[ternel]

Avec ça, J'ai ma petite idée de solution.
La valeur 35 a été dupliquée. pour moi, tu as une erreur d'indice.

Ca peut ressembler à un for qui va une case trop loin.

Essaie des tableaux pairs: {1,3,5,7}, {1,5,7,3} et {5,3,7,1}
Je regarde de mon coté.

[therwald]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
	int size = end-deb+1;
	int *tab2= new int[size];
	int k = deb;
	for (int p=0;p<size;p++)
	{
		tab2[p]=tab[p];
	}

Dans la mesure où deb n'est pas systématiquement égal à 0, en initialisant p à 0 puis en copiant les éléments de 0 à size (=end-deb) je ne suis pas sûr que tu copies les éléments cibles sur lesquels tu devrais travailler.
Je pense (à vérifier) que tu devrais copier tab[p+deb] et non tab[p].
EDIT: et adapter tes autres calculs d'indice de la même façon.

[ternel]

En effet, ca devrait mieux marcher.

Par ailleurs, aaronlbk, puisque tu es en C++, utilise le langage correctement.

Tu dispose de vector pour ton tableau, de cout<< pour l'affichage.

ce sera plus simple que printf.
Par exemple, voici ta fonction d'affichage, avec le vector (et une référence constante, parce que tu ne veux pas le copier ni modifier).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
void AfficheTableau(std::vector<int> const& tableau) {
	for(int i = 0; i < tableau.size(); ++i) {
	std::cout << '|' << tableau[i];
	}
	std::cout << '|' << std::endl;
}

[aaronlbk]

Dans la mesure où deb n'est pas systématiquement égal à 0, en initialisant p à 0 puis en copiant les éléments de 0 à size (=end-deb) je ne suis pas sûr que tu copies les éléments cibles sur lesquels tu devrais travailler.
Je pense (à vérifier) que tu devrais copier tab[p+deb] et non tab[p].
EDIT: et adapter tes autres calculs d'indice de la même façon.

Therwald J'ai essayé comme tu me l'as dit mais çà ne change rien à la sortie.

Par ailleurs Eternel, j'ai essayé avec les entrées de tableaux pairs, mais il y'a toujours des recopies des valeurs et ce nombre signé qui apparait au début
{1,5,7,3} donne |-33686019|1|3|3| en sortie
{5,3,7,1} donne |-33686019|1|3|1|
{1,3,5,7} donne|-33686019|1|3|7|
Au fait y'a t'il besoin d'écrire

std::cout<<

au lieu de

cout<<

lorsqu'on a déjà écrit

using namespace std

en tout début du code?

[jo_link_noir]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
	int size = end-deb+1;
	int *tab2= new int[size];
	for (int p=0;p<size;p++)
	{
		tab2[p]=tab[p];
	}

-> std::vector<int> tab2(tab, tab+end-deb); (sans + 1 pour la taille, c'est une erreur)

et

while (i<=mid && j <=end ) -> while (i< mid && j < end ).


S'il y a déjà un using namespace std alors mettre std:: n'est pas utile. Mais c'est mieux pour savoir d'où cela provient et ce type de using et plutôt risqué.

EDIT:
Je me suis un peu mélangé les pinceaux. Je vient de comprendre pourquoi il y avais +1... J'avoue avoir plus l'habitude des itérateurs où end correspond à la dernière valeur non accessible.

Alors pour le vecteur : vector(tab+deb, tab+end+1) sinon un mauvais intervalle est copié (comme l'a dit thewald en fait)
Par contre, la condition dans toutes les boucle devrait être avec <= et non < (l'inverse de ceux que je disait au début)
Et l'accès à tab se fait en ajoutant -deb car les indices sont maintenant décalés. Ou alors mettre après la création du tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
  i -= deb;
  j -= deb;
  end -= deb;
  mid -= deb;