LE QUICKSORT NON-RECURSIF ET L'IMPACT DE L'INSERTIONSORT SUR SES PERFORMANCES

Signaler
Messages postés
1054
Date d'inscription
samedi 2 octobre 2004
Statut
Membre
Dernière intervention
9 juillet 2013
-
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/47044-le-quicksort-non-recursif-et-l-impact-de-l-insertionsort-sur-ses-performances

Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Des réels, double ou float, se trient exactement comme des entiers signés.

Exemple pour float, il n'y a quasi rien à changer.

void __stdcall triInts(int *ptab, DWORD count)
{
int *lo, *hi, *mid, *loguy, *higuy, v;
int *lostk[STKSIZ], *histk[STKSIZ];
size_t size;
int stkptr = 0;
lo = (int*) ptab; // CAST ICI ET BASTA
...
...
Messages postés
10
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
1 avril 2012

Salut
est ce que vous pouvez me donner un exemple de quicksort non récursif pour des réels?
Merci bcp
Messages postés
536
Date d'inscription
mercredi 27 avril 2005
Statut
Membre
Dernière intervention
22 août 2008

Salut Brunews, Je suis pas entièrement d'accord avec toi sur le fait de ne pas créer une thread.
Grâce à la librairie Intel (TBB), on peut définir des seuils avant qu'une autre thread soit exécutée (granularité), ça permet lors de tri d'énormes tableaux d'utiliser le 2eme (ou plus) processeur et on est libre sur le choix de quand l'utilisation de la(/ces) thread(s) apporte un interêt.

C'est sur que dans l'absolu, si on avait pas cette librairie, dans 99% des cas, la création d'une thread serait contre productif, mais faut aussi se pencher sur les concepts qu'essaye de diffuser Intel. Je ne dis pas que c'est la panacée, mais ça a le mérite d'exister et d'être déjà pas mal efficace.

bon week end ;)
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Pour ce qui est du multi thread, je ne suis pas convaincu du tout d'aller créer un thread pour un algo restant dans les milli secondes. La crétion d'un thread risque fort de consommer autant que le temps de tri.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Salut,

le gros problème avec ce genre de tri c'est qu'il ne peut aller en prod dans un prog qui effectue des tris sur de gros tableaux pour la simple raison qu'il fait une alloc qui risque de ne pas réussir. Un algo de tri doit fonctionner à tout coup et la seule méthode certaine est un tri sur place sans aucune alloc.
On évacue la discussion sur la récursivité, il est clair que si un quicksort est récursif, il ne reste que le 'sort' mais plus du tout le 'quick'.

Essaie avec ça, j'ai fait qlqs tests et il me semble que c'est au moins aussi rapide (voire +) avec garantie de finir le tri qlq soit la taille du tableau:

#define STKSIZ (8 * sizeof(void*) - 2)

__inline void ShortsortLong(int *lo, int *hi)
{
int *p, *max, v;
while(hi > lo) {
max = lo;
for(p = lo + 1; p <= hi; p++) {
if(*p > *max) max = p;
}
v *max; *max *hi; *hi = v;
hi--;
}
}

void __stdcall triInts(int *ptab, DWORD count)
{
int *lo, *hi, *mid, *loguy, *higuy, v;
int *lostk[STKSIZ], *histk[STKSIZ];
size_t size;
int stkptr = 0;
lo = ptab;
hi = lo + (count - 1); /* DERNIER ELEM */
recurse:
size = (hi - lo) / sizeof(long) + 1; /* NBR ELEMS A TRIER */
if(size <= 8) {
ShortsortLong(lo, hi);
goto goSTACK;
}
mid = lo + (size / 2); /* ELEM CENTRAL */
if(*lo > *mid) {v *lo; *lo *mid; *mid = v;}
if(*lo > *hi) {v *lo; *lo *hi; *hi = v;}
if(*mid > *hi) {v *mid; *mid *hi; *hi = v;}
loguy = lo;
higuy = hi;
for(;;) {
if(mid > loguy) {
do {
loguy++;
} while(loguy < mid && *loguy <= *mid);
}
if(mid <= loguy) {
do {
loguy++;
} while(loguy <= hi && *loguy <= *mid);
}
do {
higuy--;
} while (higuy > mid && *higuy > *mid);
if(higuy < loguy) break;
v *loguy; *loguy *higuy; *higuy = v;
if(mid higuy) mid loguy;
}
higuy++;
if(mid < higuy) {
do {
higuy--;
} while(higuy > mid && *higuy == *mid);
}
if(mid >= higuy) {
do {
higuy--;
} while(higuy > lo && *higuy == *mid);
}
if(higuy - lo >= hi - loguy) {
if(lo < higuy) {
lostk[stkptr] = lo;
histk[stkptr] = higuy;
++stkptr;
}
if(loguy < hi) {
lo = loguy;
goto recurse;
}
}
else {
if(loguy < hi) {
lostk[stkptr] = loguy;
histk[stkptr] = hi;
++stkptr;
}
if(lo < higuy) {
hi = higuy;
goto recurse;
}
}
goSTACK:
if(--stkptr >= 0) {
lo = lostk[stkptr];
hi = histk[stkptr];
goto recurse;
}
}
Afficher les 7 commentaires