home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_07_04 / v7n4091a.txt < prev    next >
Text File  |  1988-09-05  |  2KB  |  73 lines
  1. /* An efficient linked list sort function */
  2. /* Philip J. Erdelsky - September 6, 1988 */
  3.  
  4. #include <stdio.h>
  5.  
  6. struct link {
  7.   struct link *next;
  8.   /* other members not directly accessed by llsort() */
  9.   };
  10.  
  11. struct link *llsort(p, compare) struct link *p; int (*compare)(); {
  12. int base;
  13. unsigned int block;
  14.  
  15. struct tape {
  16.   struct link first, *last;
  17.   unsigned int count;
  18.   } tape[4];
  19.  
  20. tape[0].count = 0; tape[0].last = &tape[0].first;
  21. tape[1].count = 0; tape[1].last = &tape[1].first;
  22.  
  23. for (base=0; p!=NULL; p=p->next, base^=1) {
  24.   tape[base].last = tape[base].last->next = p;
  25.   tape[base].count++;
  26.   }
  27.  
  28. for (base=0, block=1; tape[base+1].count!=0; base^=2, block<<=1) {
  29.   int dest;
  30.   struct tape *tape0, *tape1;
  31.   tape0 = tape + base;
  32.   tape1 = tape + base + 1;
  33.   dest = base^2;
  34.   tape[dest].count = 0; tape[dest].last = &tape[dest].first;
  35.   tape[dest+1].count = 0; tape[dest+1].last = &tape[dest+1].first;
  36.   for (; tape0->count!=0; dest^=1) {
  37.     unsigned int n0, n1;
  38.     struct tape *output_tape;
  39.     output_tape = tape + dest;
  40.     n0 = n1 = block;
  41.     while (1) {
  42.       struct link *chosen_item;
  43.       struct tape *chosen_tape;
  44.       if (n0==0 || tape0->count==0) {
  45.         if (n1==0 || tape1->count==0) break;
  46.         chosen_tape = tape1;
  47.         n1--;
  48.         }
  49.       else if (n1==0 || tape1->count==0) {
  50.         chosen_tape = tape0;
  51.         n0--;
  52.         }
  53.       else if ((*compare)(tape0->first.next,tape1->first.next)>0) {
  54.         chosen_tape = tape1;
  55.         n1--;
  56.         }
  57.       else {
  58.         chosen_tape = tape0;
  59.         n0--;
  60.         }
  61.       chosen_tape->count--;
  62.       chosen_item = chosen_tape->first.next;
  63.       chosen_tape->first.next = chosen_item->next;
  64.       output_tape->last = output_tape->last->next = chosen_item;
  65.       output_tape->count++;
  66.       }
  67.     }
  68.   }
  69.  
  70. tape[base].last->next = NULL;
  71. return tape[base].first.next;
  72. }
  73.