zekhninisaber | 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 :
- void TriFusion(typeListItem * list) {
- // Trivial case.
- if (!list || !list->NextItem)
- return list;
- typeListItem *right = list,
- *temp = list,
- *last = list,
- *result = 0,
- *next = 0,
- *tail = 0;
- // Find halfway through the list (by running two pointers, one at twice the speed of the other).
- while (temp && temp->NextItem) {
- last = right;
- right = right->NextItem;
- temp = temp->next->NextItem;
- }
- // Break the list in two. (prev pointers are broken here, but we fix later)
- last->NextItem = 0;
- // Recurse on the two smaller lists:
- list = TriFusion(list);
- right = TriFusion(right);
- // Merge:
- while (list || right) {
- // Take from empty lists, or compare:
- if (!right) {
- next = list;
- list = list->NextItem;
- } else if (!list) {
- next = right;
- right = right->NextItem;
- } else if ( ( SortKey == SortNbr ?
- (*(float *) ((char *)AuxItem+ListOffset[SortKey]) - *(float *) ((char *)CurItem+ListOffset[SortKey])) :
- strcmp ( (char *)AuxItem+ListOffset[SortKey], (char *)CurItem+ListOffset[SortKey] ) ) < 0 ) {
- // if (AuxItem < CurItem) : SWAP
- next = list;
- list = list->NextItem;
- } else {
- next = right;
- right = right->NextItem;
- }
- if (!result) {
- result=next;
- } else {
- tail->NextItem=next;
- }
- tail = next;
- }
- return result;
- }
|
|
