Tri Rapide sur un CLIST

Version imprimable

06/07/2005, 17h36
ensisoft

Tri Rapide sur un CLIST

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

voila ma fonctoin qui fait le tri de maListe dans maListeTemp

Code:

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 ;
}

07/07/2005, 09h02
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.
07/07/2005, 13h19
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:

1 2 3 4 5 6 POSITION pPos = maListe.GetHeadPosition(); for (int i=0;i < maListe.GetCount();i++) { CElement Element = maListe.GetNext(pos); //...........
:D
07/07/2005, 13h38
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.
11/07/2005, 15h28
ensisoft
Citation:
Envoyé par 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:

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

:D
J'ai pensé que ceci permettrai de liberer de la memoire
11/07/2005, 15h37
farscape

salut,
tu peux toujours appeler RemoveAll( ); a la fin ...
tu as tester pour la vitesse ?
:D
11/07/2005, 16h00
ensisoft

Citation:

Envoyé par farscape

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

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
12/07/2005, 09h52
ensisoft

Citation:

Envoyé par ensisoft

Citation:

Envoyé par farscape

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

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? :pleure:
13/12/2005, 23h22
laurentwiller

Une solution de tri rapide parmi tant d'autres

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.