C tri par fusion

C tri par fusion - C - Programmation

Marsh Posté le 17-08-2015 à 12:44:49    

Bonjour à tous,
 
j'ai sous la main cette fonction de tri par fusion que je ne comprend pas. Quelqu'un saurait-il m'expliquer grosso modo ligne par ligne ce qu'elle fait ?
Aussi y'a-t-il possibilité de l'écrire de manière plus simple que ça ?
Merci
 

Code :
  1. void TriFusion(typeListItem * list) {
  2.     // Trivial case.
  3.     if (!list || !list->NextItem)
  4.       return list;
  6.     typeListItem *right = list,
  7.           *temp  = list,
  8.           *last  = list,
  9.           *result = 0,
  10.           *next   = 0,
  11.           *tail   = 0;
  13.     // Find halfway through the list (by running two pointers, one at twice the speed of the other).
  14.     while (temp && temp->NextItem) {
  15.       last = right;
  16.       right = right->NextItem;
  17.       temp = temp->next->NextItem;
  18.     }
  20.     // Break the list in two. (prev pointers are broken here, but we fix later)
  21.     last->NextItem = 0;
  23.     // Recurse on the two smaller lists:
  24.     list = TriFusion(list);
  25.     right = TriFusion(right);
  27.     // Merge:
  28.     while (list || right) {
  29.       // Take from empty lists, or compare:
  30.       if (!right) {
  31.         next = list;
  32.         list = list->NextItem;
  33.       } else if (!list) {
  34.         next = right;
  35.         right = right->NextItem;
  36.       } else if ( ( SortKey == SortNbr ?
  37.                 (*(float *) ((char *)AuxItem+ListOffset[SortKey]) - *(float *) ((char *)CurItem+ListOffset[SortKey])) :
  38.                 strcmp ( (char *)AuxItem+ListOffset[SortKey], (char *)CurItem+ListOffset[SortKey] ) ) < 0  ) {
  39.         // if (AuxItem < CurItem) : SWAP
  40.         next = list;
  41.         list = list->NextItem;
  42.       } else {
  43.         next = right;
  44.         right = right->NextItem;
  45.       }
  46.       if (!result) {
  47.         result=next;
  48.       } else {
  49.         tail->NextItem=next;
  50.       }
  51.       tail = next;
  52.     }
  53.     return result;
  54.   }


Reply

Marsh Posté le 17-08-2015 à 12:44:49   

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed