Csortedarray<template> visual c++ mfc

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 047 fois - Téléchargée 29 fois

Contenu du snippet

Une classe template dérivée du CArray des MFC
J'ai ajouté des méthodes de tri qui manquent cruellement
Vu que je manipule beaucoup de données au boulot, je m'en sert souvent

AddSorted(element) : ajoute "element" par insertion après recherche de sa position par dichotomie
Sort() : tri la table à l'aide d'un qSort
PartialSort(start, end) : tri une partie de la table avec qSort
Swap(src,dst) : échange 2 éléments dans la table

j'ai laissé les méthodes de tri partiel et de swap en public vu qu'elles ont leur utilité pour moi

Source / Exemple :


#pragma once

#include "afxtempl.h"

// Classe dérivée de CArray en reprenant toutes les capacités
// Ajout de méthodes de tri et d'ajout par insertion avec recherche de position par dichotomie
template <class TYPE, class ARG_TYPE = const TYPE&>
class CSortedArray : public CArray<TYPE, ARG_TYPE>
{
public:
	INT_PTR AddSorted(TYPE newElement); // Ajout par insertion avec recherche de position par dichotomie
	void Sort(void) { QuickSort(0, GetCount()-1); } // Effectue un tri complet de la table à l'aide la méthode QuickSort
	void PartialSort(INT_PTR startIndex, INT_PTR endIndex); // Effectue un tri partiel de la table
	void Swap(INT_PTR src, INT_PTR dst) { TYPE tmp=GetAt(src); SetAt(src, GetAt(dst)); SetAt(dst, tmp); } // Echange 2 éléments dans la table

protected:
	void QuickSort(INT_PTR startIndex, INT_PTR endIndex);
};

// Ajoute un élément à la table par insertion en recherchant sa position par dichotomie
// Entrée : le nouvel élément à ajouter
// Sortie : l'index dans la table où le nouvel élément a été ajouté
template <class TYPE, class ARG_TYPE>
AFX_INLINE INT_PTR CSortedArray<TYPE, ARG_TYPE>::AddSorted(TYPE newElement)
{
	INT_PTR start = 0, end = GetCount();
	while(start < end)
	{
		INT_PTR pos = (start + end) / 2;
		if(newElement > GetAt(pos))
			start = pos + 1;
		else
			end = pos;
	}
	InsertAt(start, newElement);
	return start;
}

// Effectue un tri QuickSort des éléments compris entre les index "A" et "B" (inclus)
// Entrée : l'index du premier élément et l'index du dernier élément à trier
template <class TYPE, class ARG_TYPE>
AFX_INLINE void CSortedArray<TYPE, ARG_TYPE>::PartialSort(INT_PTR startIndex, INT_PTR endIndex)
{
	if(startIndex < 0)
		startIndex = 0;

	if(endIndex >= GetCount())
		endIndex = GetCount() - 1;

	if(startIndex >= endIndex)
		return;

	QuickSort(startIndex, endIndex);
}

// Méthode de tri QuickSort d'une portion de la table
// Entrée : l'index du premier élément à trier et l'index du dernier élément à trier
template <class TYPE, class ARG_TYPE>
AFX_INLINE void CSortedArray<TYPE, ARG_TYPE>::QuickSort(INT_PTR startIndex, INT_PTR endIndex)
{
	if(startIndex >= endIndex)
		return;

	if(startIndex == endIndex - 1)
	{
		if(GetAt(startIndex) > GetAt(endIndex))
			Swap(startIndex, endIndex);
		return;
	}

	INT_PTR startToEnd = startIndex, endToStart = endIndex;

	Swap((startToEnd + endToStart) / 2, endToStart);

	TYPE middle = GetAt(endToStart);

	while(startToEnd < endToStart)
	{
		while(GetAt(startToEnd) <= middle && startToEnd < endToStart) startToEnd++;
		while(middle <= GetAt(endToStart) && startToEnd < endToStart) endToStart--;
		if(startToEnd < endToStart)
			Swap(startToEnd, endToStart);
	}

	SetAt(endIndex, GetAt(endToStart));
	SetAt(endToStart, middle);

	QuickSort(startIndex, startToEnd - 1);

	QuickSort(endToStart + 1, endIndex);
}

Conclusion :


J'ai séparé la fonction de comparaison pour pouvoir la modifier facilement à votre convenance, par exemple pour trier dans l'ordre croissant ou décroissant

A voir également

Ajouter un commentaire

Commentaires

Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

l'algo que j'utilisais posait trop de problèmes, j'ai donc recherché un autre algo et j'en ai trouvé un sur le site suivant :
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
(il s'agit du quicksort "simple")

vous pouvez toujours vous amuser à l'améliorer en combinant plusieurs tris
Messages postés
229
Date d'inscription
dimanche 14 septembre 2003
Statut
Membre
Dernière intervention
20 août 2014

Il s'agit simplement d'un héritage de CArray MFC, l'utilisation est la même, tu déclares ta donnée :
CSortedArray<CString> arStrs;

tu ajoutes des données avec : arStrs.Add(donnee);
puis tu tries le tableau avec : arStrs.Sort();
ou tu ajoutes directement la donnée avec : arStrs.AddSorted(donnee);
qui insèrera là donnée après avoir recherché la bonne place et qui renverra sa position

concernant tes tableaux à 3 dimensions par contre, il va faloir que tu modifies la classe ou que tu récupères la fonction de tri pour la reprendre
dans son état actuel cette classe ne te permettra pas de faire ce que tu cherches je pense
Messages postés
1
Date d'inscription
lundi 27 janvier 2003
Statut
Membre
Dernière intervention
17 octobre 2005

J'ai des tableaux à trois dimensions à trier. Il est possible que ce code reponde aux besoins mais un exemple avec cette classe , meme simple , aurait ete le bien venu..
Messages postés
199
Date d'inscription
vendredi 16 avril 2004
Statut
Membre
Dernière intervention
28 février 2008

toujours utile...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.