C++

Méthode de tri

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Méthode de tri

Amonchakai

Bonjour !

En ce moment je suis en train de m'amuser a trier des entiers contenu dans un tableau. je sais il y a la STL qui fait ça super bien, rapide et tout... Mais bon aujourd'hui je réinvente la roue . J'ai créé mon petit algorithme... bon je sais il est sûrement pas efficace (une fois qu'il marchera j'irais voir Google pour en trouver des meilleurs...)

voilà :

Code :

#include <iostream>
int main(int argc, char **argv)
{
int tab[] = {1, 6, 4, 3, 2, 8, 10, 9, 5, 12};
int index=0, min;
for(int i = 0 ; i < 10 ; i++)
{
min = tab[i];
for(int n = i ; n < 10 ; n++)
if(min > tab[n])
{
index = n;
min = tab[n];
}
std::cout<<"Le min c'est : "<<min<<"---";
for(int n = i ; n < 10 ; n++)
std::cout<<tab[n]<<" ";
std::cout<<std::endl;
int temp = tab[index];
tab[index] = tab[i];
tab[i] = temp;
}
for(int i = 0 ; i < 10 ; i++)
std::cout<<tab[i]<<" ";
std::cout<<std::endl;
return 0;
}

Bon le soucis c'est qu'a la sortie il me sort ça :

Citation :

Le min c'est : 1---1 6 4 3 2 8 10 9 5 12
Le min c'est : 2---6 4 3 2 8 10 9 5 12
Le min c'est : 3---6 4 3 8 10 9 5 12
Le min c'est : 4---6 4 8 10 9 5 12
Le min c'est : 5---6 8 10 9 5 12
Le min c'est : 6---6 8 10 9 12
Le min c'est : 8---8 10 9 12
Le min c'est : 9---10 9 12
Le min c'est : 9---9 12
Le min c'est : 12---12

1 2 3 4 5 6 8 10 12 9

comme on peut le voir il y a un souci sur les trois dernières lignes (avec l'histoire du 9). Est-ce que vous voyez le problème, je suis sûr que ça doit être bête mais je vois pas...

Merci

[edit] j'ai trouvé le nom de ma méthode : tri par sélection...

Message édité par Amonchakai le 09-09-2006 à 18:48:34

Publicité

nargy

Andouille!!!
ligne 6: tu initialise <<min>> mais pas <<index>>
(or il se trouve qu'à un moment donné pour min=6 c'est à la fois le minimum et le premier élément du sous-tableau non trié, et qu'<<index>> est celui de l'élément précédamment minimum)

Message cité 2 fois
Message édité par nargy le 09-09-2006 à 20:27:09

Amonchakai

nargy a écrit :

pardon... pardon... je vais de ce pas m'autoflageller, je recommencerais pas promis...

Merci

Sve@r

nargy a écrit :

Andouille!!!
ligne 6: tu initialise <<min>> mais pas <<index>>

[:rofl]

Message édité par Sve@r le 10-09-2006 à 12:43:22

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.

slash33

Les compilos ne détectent pas les variables non initialisées ?

nargy

Il s'agit sur certains compilos d'une option facultative.

Amonchakai

Surtout que la il y avait aucunne chance qu'il prévienne puisque index avait été initialisé ligne 6 au moment de sa déclaration et qu'il fallait que je l'initialise a la valeur de i dans le premier for() a la ligne 10...

slash33

:??:

Amonchakai

Bonjour !

Me revoila avec un nouvel algorithme de tri... Après le tri par sélection, le tri par insertion, le tri a bulle voici le tri par fusion !
Bon je tient tout d'abord a prévenir mon algo marche mais j'aimerais bien avoir votre avis sur ce que j'ai écrit (en fait pour savoir si il pue pas trop ) par ce que des quatres c'est celui qui est le plus volumineux donc j'aimerais savoir si j'ai pas compliqué le problème...

Voilà

Code :

#include<iostream>
void triFusion(int* tab, int length);
int main(int argc, char** argv)
{
int tab[] = {1, 8, 5, 3, 9, 2, 6, 4, 7, 0};
triFusion(tab, sizeof(tab)/4);
for(int i = 0 ; i < 10 ; i++)
std::cout<<tab[i]<<" ";
std::cout<<std::endl;
}
void triFusion(int* tab, int length)
{
if(length == 1) //cas trivial
return;
int *ssTab1, *ssTab2;
int taille1, taille2;
// allocation de mem pour les ssTabs
if(length%2 == 0)
taille1 = taille2 = length/2;
else
{
taille1 = length/2;
taille2 = length/2+1;
}
ssTab1 = new int[taille1];
ssTab2 = new int[taille2];
//remplissage des ssTabs
for(int i = 0 ; i < length/2 ; i++)
{
ssTab1[i] = tab[i];
ssTab2[i] = tab[i+length/2];
}
if(length%2 == 1)
ssTab2[length/2] = tab[length-1];
//Tri des ssTabs
triFusion(ssTab1, taille1);
triFusion(ssTab2, taille2);
//regroupement des ssTabs
int index1 = 0, index2 = 0;
for(int i = 0 ; i < length ; i++)
{
if(index1 == taille1)
{
tab[i] = ssTab2[index2];
index2++;
continue;
}
if(index2 == taille2)
{
tab[i] = ssTab1[index1];
index1++;
continue;
}
if(ssTab1[index1] <= ssTab2[index2])
{
tab[i] = ssTab1[index1];
index1++;
}
else
{
tab[i] = ssTab2[index2];
index2++;
}
}
delete[] ssTab1;
delete[] ssTab2;
}

dans le genre des truc qui pue il y a ma partie regroupement des tableaux que je trouve pas belle... mais j'ai pas trouvé mieux...

Merci de me donner votre avis

Message édité par Amonchakai le 10-09-2006 à 18:04:24

nargy

au moins il ya des commentaires
lignes 53-65: il me semble que tu peux les mettre après la boucle.

Publicité

Amonchakai

tu veut dire de mettre ça:

Code :

if(index1 == taille1)
{
tab[i] = ssTab2[index2];
index2++;
continue;
}
if(index2 == taille2)
{
tab[i] = ssTab1[index1];
index1++;
continue;
}

après ça :

Code :

if(ssTab1[index1] <= ssTab2[index2])
{
tab[i] = ssTab1[index1];
index1++;
}
else
{
tab[i] = ssTab2[index2];
index2++;
}

???
mais je risque de sortir de mes tableaux non ? c'etait justement pour ça que j'avais mis mes premiers test...

Et Merci de me donner ton avis

ps : au sujet des comentaires c'est vrai que j'ai fait un effort pour forcer a en mettre

nargy

Bon... En étudiant ton code, je me rends compte que j'ai sûrement dit une connerie.
Je me basais sur le fait que taille2-taille1<=1 et sur les lignes 56 et 63, qui malheureusement sont fausses.
J'explique:
tu teste index1==taille1, et si ce test est vrai tu incrémente index1. Or, index1 cette fois dépasse taille1 donc au prochain tour de boucle taille1!=index1. Celà ne pose pas de problème dans ton exemple (?), mais si par exemple tous les éléments du sstab1 sont inférieurs à ceux de sstab2, tu va épuiser les éléments de sstab1 avant ceux de sstab2, et faire déborder index1.
Idem pour taille2 et index2.

Message cité 1 fois

nargy

Tu devrais essayer de faire tourner le programme avec un tableau de taille impaire pour voir s'il y d'autres bugs. (a priori non, mais ça peut servir de tester)

Edit: Perso je protègerais le if de la ligne 67 avec un test index1<taille1 et index2<taille2, pour faire trois cas: index1 épuisé, index2 épuisé, aucun des deux épuisés. Si l'un des deux est épuisé tu peut te contenter de recopier le reste de l'autre sous-tableau avec un memcpy.

Message édité par nargy le 10-09-2006 à 18:48:23

Amonchakai

nargy a écrit :

Oui, c'est justement l'objectif de mes deux premiers test dans ma boucle for()... Mais je croit que tu as pas bien vu ce que j'ai fait car quand j'ai index1==taille1 ce n'est plus index1 que j'incrémente mais index2... Ayant mis tous les éléments de ssTab1 je met maintenant tous ceux de ssTab2.

Sinon on a bien toujours taille2-taille1<=1

nargy

Ha oui exact, j'ai mal lu... ma suggestion d'utiliser memcpy reste valable.

Amonchakai

j'avais pas vu memcpy()... Ok je vais mettre ça

Amonchakai

Heu il y a un soucis avec memcpy()... car quand je regarde ce qu'ils disent là :
http://www.linux-kheops.com/doc/ma [...] html#sect0

Je vais avoir mon tableau tab qui va être écrasé au lieu d'être complété non ?
Et puis pour copier la fin de ssTab1 (respectivement ssTab2) il va falloir que je crée un autre tableau, car memcpy() copie n octets a partir du début de la zone mémoire pointé par ssTab1 non ?

nargy

arithmétique de pointeurs...

Code :

// copier à partir de debut_source jusqu'à fin_source vers debut_dest:
memcpy(dest+debut_dest, source+debut_source, fin_source-debut_source*sizeof(int));

Message cité 1 fois

Amonchakai

nargy a écrit :

arithmétique de pointeurs...

Code :

// copier à partir de debut_source jusqu'à fin_source vers debut_dest:
memcpy(dest+debut_dest, source+debut_source, fin_source-debut_source*sizeof(int));

Ha bha je connais pas... :??:
Voilà un truc de base auquel je suis passé à côté...
Bon, il va falloir que j'aprenne ça.

Merci

Amonchakai

Salut !
Bon je viens de regarder l'arithmétique des pointeurs. Et je comprend pas bien ce que c'est que la différence de deux pointeurs. Car sur le site que j'ai trouvé ils disent ça :

Citation :

Le type du résultat de la soustraction de deux pointeurs est très dépendant de la machine cible et du modèle mémoire du programme. En général, on ne pourra jamais supposer que la soustraction de deux pointeurs est un entier (que les chevronnés du C me pardonnent, mais c'est une erreur très grave). En effet, ce type peut être insuffisant pour stocker des adresses (une machine peut avoir des adresses sur 64 bits et des données sur 32 bits). Pour résoudre ce problème, le fichier d'en-tête stdlib.h contient la définition du type à utiliser pour la différence de deux pointeurs. Ce type est nommé ptrdiff_t.

bon quand il dit : "on ne pourra jamais supposer que la soustraction de deux pointeurs est un entier" en même temp ça me serait pas venu a l'idée... Et ensuite quand il dit "Ce type est nommé ptrdiff_t" c'est super mais c'est quoi ? un pointeur j'imagine mais sur quelle zone mémoire ?

Merci

nargy

Te prends pas la tête.
Dans l'exemple que je t'ai donné, on ne stocke pas la différence des pointeurs, on la donne tel quel à memcpy.
Sur une machine avec des pointeurs 64bits, la différence de deux pointeurs est 64 bits, or pour pouvoir copier des zones mémoires memcpy doit donc utiliser une taille de 64bits. Sizeof() retourne lui aussi un entier 64bits.

Amonchakai

Ok, donc au final ça donne ça :

Code :

//regroupement des ssTabs
int index1 = 0, index2 = 0;
for(int i = 0 ; i < length ; i++)
{
if(index1 == taille1)
{
memcpy(tab+i, ssTab2+index2, (taille2-index2)*sizeof(int));
break;
}
if(index2 == taille2)
{
memcpy(tab+i, ssTab1+index1, (taille1-index1)*sizeof(int));
break;
}
if(ssTab1[index1] <= ssTab2[index2])
{
tab[i] = ssTab1[index1];
index1++;
}
else
{
tab[i] = ssTab2[index2];
index2++;
}
}
delete[] ssTab1;
delete[] ssTab2;
}

Et ça marche impec...

Mais bon dans ce cas on a juste l'addition de pointeurs avec des entier... La Ok pas de problème, je comprend ce que ça fait. Mais la différence de deux pointeurs c'est la première fois que j'en endend parler. C'est pour ça que je voulais essayer de comprendre ce que cela pouvait bien donner... (et je note qu'ils ont parlé de différence mais pas d'addition... :??: )

Bon en gros tu me conseille de faire l'impasse dessus, c'est pas important ?

nargy

La différence entre deux pointeurs, est la différence entre deux positions en mémoire, c'est donc une longueur (intervalle de mémoire).
Le problème peut survenir quand la taille totale de mémoire est supérieure à celle d'un entier, dans ce cas si tu mets une différence entre deux pointeurs (la mesure d'un intervalle de mémoire a le même nombre de bits qu'un pointeur) dans un entier tu perds des bits. Comme quand tu essaye de faire tenir 64bits dans 32bits.
Ce n'est pas le cas avec le memcpy que tu as fait.

Amonchakai

D'accord, Merci beaucoup nargy

nargy

A oui, j'oubliais, l'addition de pointeurs n'a pas de signification. Par contre une position + une longueur donne une nouvelle position.

Publicité

FORUM HardWare.fr

Programmation

C++

Méthode de tri

Sujets relatifs
problème : méthode Cells de l'objet global a échoué	Methode 'Paste' de l'objet -Worksheet' a échoué
[Resolu][C#.NET] Appel methode static impossible ?	[C#] Passer mon propre objet à ma Web Methode
[RESOLU] EJB : Problème méthode findAll() avec Jonas	Conception et methode statique
La meilleure méthode pour modifier un xml?	question méthode RDM c'est quoi ?
utiliser une méthode booléenne	Warning suite a utilisation d'une référence dans une méthode [RESOLU]
Plus de sujets relatifs à : Méthode de tri

Page générée en 0.125 secondes