Bonjour,

Dans un projet sur lequel je bosse en ce moment, je dois implémenter un tri.

Jusque là, rien de très complexe...

Mais voila, quel algo choisir ?

Voici les détails :

Je doit trier un "buffer" de structures, qui ressemble à ça :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
struct sEvenement
{
   int   m_position;
   char  m_data01;
   char  m_data02;
   char  m_data03;
   char  m_data04;
};
Le buffer est déclaré comme ça :
(attention, le tableau evenements est bien un tableau de pointeurs vers des evenements alloués en mémoire)

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
struct sEvenementsBuffer
{
   int           numEvenements;
   sEvenement*   evenements[MAX_EVEMENTS];
};
Bon, j'ai pas choisi le format de mes données, c'était là avant moi...

Je dois ecrire une fonction qui prend une structure sEvenementsBuffer en entrée et tri son tableau d'evenements par m_position croissante.

Il suffit donc de trier les pointeurs dans le tableau en fonction de :
evenements[i]->m_position

Voila les contraintes :

- 1024 éléments au maximum
- entre 50 et 100 éléments quand le système est "en charge"
- entre 0 et 20 éléments quand le système est "pépére"
- à priori, les données n'ont aucune raison d'être "presque triées" à l'avance
- ça doit aller très très vite

D'après ce que j'ai trouvé ici :
http://fr.wikipedia.org/wiki/Algorithme_de_tri

- le tri par insertion est le plus rapide pour de petites listes
- le "quicksort" est le plus rapide pour de plus grandes listes

Pour l'instant, je suis parti sur l'idée d'implémenter plusieurs algo en fonction du nombre d'éléments à trier.

Auriez-vous une super idée pour avoir un truc réélement efficace ?