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

Commentaire de Pistol_Pete le 18/06/2008 09:41:06

Salut

Voila mes resultats pour 10 millions:  166 ms
AMD Athlon 64 X2 Dual
Core processor 6000+
3 GHz
XP sp3

Et puisse que l'on parle de performance, je ne comprend pas pourquoi ce programme n'est pas multithread...
Utiliser la moitier de la puissance de son PC, ca ne te gene pas?
Je suis sur que pour des plus grandes listes le gain sera immense. Ca serai cool de pouvoir tester.

A+

Commentaire de BruNews le 18/06/2008 19:56:57 administrateur CS

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