Discussion :

[ensisoft]

Bonjour tout le monde
Je cherche un algorithme de tri rapide sur l'objet CList
j'utilise deja un mais ça prend beaucoup de temps
quelqu'un a une idee
Merci d'avance

[ensisoft]

voila ma fonctoin qui fait le tri de maListe dans maListeTemp

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
 
void OrdonnerListe ()
{
	POSITION pPosTemp;
	CElement ElementTemp;
	POSITION pPos = maListe.GetHeadPosition();
	while (pPos)
	{
		CElement Element = maListe.GetAt(pPos);
		pPosTemp = maListeTemp.GetHeadPosition();
		bool bSup = false;
		while (pPosTemp && !bSup)
		{
			ElementTemp = maListeTemp.GetAt(pPosTemp);
			if(Element.dtDate.IsLessThan(ElementTemp.dtDate))
				bSup = true;
			else
				maListeTemp.GetNext(pPosTemp);			
		}
 
		if (pPosTemp)
			maListeTemp.InsertBefore(pPosTemp, Element);
		else	
			maListeTemp.AddTail(Element);
		maListe.RemoveHead();
		pPos = maListe.GetHeadPosition();
	}
	return ;
}

[Laurent Gomila]

En standard, tu as sort pour trier. Par contre étant donné que tu bosses avec une CList, je ne pense pas que ça t'aidera beaucoup. Je déplace ton sujet sur le forum VC++, merci de poster au bon endroit à l'avenir.

[farscape]

salut,
une optimisation simple de ton code :
parcourir la liste ,plutot que de prendre le premier element et le detruire ce qui oblige un tassement de la liste a chaque fois:

Code :

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

1
2
3
4
5
6
 
POSITION pPos = maListe.GetHeadPosition();
for (int i=0;i < maListe.GetCount();i++)
{
CElement Element = maListe.GetNext(pos);
//...........

[DamessS]

Bonjour.

Je ne pas bien compris votre code. (Si vous pouviez le commenter).
A votre place, je ne déclarerais aucune variable dans une boucle.

[ensisoft]

salut,
une optimisation simple de ton code :
parcourir la liste ,plutot que de prendre le premier element et le detruire ce qui oblige un tassement de la liste a chaque fois:

Code :

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

1
2
3
4
5
6
 
POSITION pPos = maListe.GetHeadPosition();
for (int i=0;i < maListe.GetCount();i++)
{
CElement Element = maListe.GetNext(pos);
//...........

J'ai pensé que ceci permettrai de liberer de la memoire

[farscape]

salut,
tu peux toujours appeler RemoveAll( ); a la fin ...
tu as tester pour la vitesse ?

[ensisoft]

salut,
tu peux toujours appeler RemoveAll( ); a la fin ...
tu as tester pour la vitesse ?

Non mais je voulais gagner de la memoire pendant le tri
parce que la boucle de tri consomme enormement de ressources
si tu voix que cette operation est tres couteuse en temps de reponse je vais essayer d'adopter ton idee
Merci

[ensisoft]

salut,
tu peux toujours appeler RemoveAll( ); a la fin ...
tu as tester pour la vitesse ?

Non mais je voulais gagner de la memoire pendant le tri
parce que la boucle de tri consomme enormement de ressources
si tu voix que cette operation est tres couteuse en temps de reponse je vais essayer d'adopter ton idee
Merci

j'ai fait le test et voici les resultats
ma methode avec des remvehead : 50mn
ta methode avec getnext : 59mn
donc ce n'est pas ça la solution
quelqu'un a une autre idée?

[laurentwiller]

Le principe consiste à parcourir du début jusqu'à la fin de ta liste tant que le tri est décroissant. Si décroissant, on permute l'élément précédent et l'élement suivant. Chaque boucle consécutive est dégressive d'1 pas car à la fin de chaque boucle vous aurez obligatoirement le plus grand élément à la dernière itération (en d'autre terme c'était votre pivot).

Exemple:
Vous avez une liste de 4 chiffres que vous voulez rendre croissant: 9/8/7/6

Départ : 9/8/7/6
==== 1ere boucle de 0 à 2 ou de 0 à N-1 éléments ====
1ère permutation : 8/9/7/6 i=0
2ème permutation : 8/7/9/6 i=1
3ème permutation : 8/7/6/9 i=2

==== 2ème boucle de 0 à 1 ou de 0 à N-2 éléments ====
1ère permutation : 7/8/6/9 i=0
2ème permutation : 7/6/8/9 i=1

==== 3ème boucle de 0 à 0 ou de 0 à N-3 éléments ====
1ère permutation : 6/7/8/9 i=0

Pour résumer, vous avez ici le pire des cas avec N éléments, car nous avons une inversion totale. Donc dans ce cas, le maximum de boucles avec N éléments est N-1 boucles, le maximum de permutations est (N-1)*(N-2)*(N-3)* .... * 1 ou (N-1)!.

Une autre solution consiste à faire une récursivité muni d'un pivot. Mais c'est plus compliqué. Essayez déjà avec ça, c'est déjà beaucoup plus rapide.

Bien cordialement.