home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d5xx / d502 / cells.lha / CELLS / CELLSSource.lzh / mSort.c < prev   
C/C++ Source or Header  |  1991-04-20  |  13KB  |  350 lines
  1. /*
  2.  *  MSORT.C             version 2.0             17-Nov-1989
  3.  *
  4.  *  A general-purpose implementation of a merge-sort for linked lists.
  5.  *
  6.  *  Written for the Commodore Amiga 1000, version 1.3
  7.  *  using Lattice C v4.0 by Davide P. Cervone
  8.  *
  9.  *  The merge-sort algorithm takes advantage of the fact that it is
  10.  *  easy to combine two sorted lists into one sorted list:  just keep
  11.  *  taking the smaller item off the top of the two lists and add it
  12.  *  to the bottom of the new list until the original lists are empty.
  13.  *
  14.  *  The sort algorithm first places each item to be sorted is in its
  15.  *  own list (one item long).  Pairs of these singleton lists are merged
  16.  *  in the manner described above, and we are left with half as many lists
  17.  *  as before, each two items long.  Pairs of these lists are combined to
  18.  *  form half as many lists again, each four items long.  This process is 
  19.  *  repeated until only one list remains.  This is the final, sorted list.
  20.  *
  21.  *  The merge-sort is ideal for linked lists, since it does not require
  22.  *  random access look-ups (which are difficult in linked-lists).  It does 
  23.  *  not require extra "work-space", so no memory is wasted.  Finally, its 
  24.  *  result is a simple, linked-list structure, ready to use (unlike some sort 
  25.  *  methods that result in trees or other structures were it is dificult to 
  26.  *  get from one item to the next).
  27.  *
  28.  *  The merge-sort is fairly efficient.  In it's worst case, it takes
  29.  *  n * (log(n) - 1) + 1 comparisons to sort  n  items (where the log() 
  30.  *  function is the log to base 2).  Thus, for 1024 items, the maximum 
  31.  *  number of comparisons is 1024*(10-1)+1 = 9217, or approximately 9
  32.  *  comparisons per item.  And that's its worst case!  Compare this to
  33.  *  a worst case of n*(n-1)/2 for some popular sorts (e.g., the tree sort).  
  34.  *  The worst case for the tree sort for 1024 items is 523776 compares!
  35.  *
  36.  *  In its best case, the merge-sort takes  n * log(n) / 2  comparisons.
  37.  *  For our example of n=1024, that's 5120 comparisons.  For the tree sort,
  38.  *  the minimum is approximately  n * (log(n) - 2)  comparisons, for a 
  39.  *  minimum of 8192 comparisons for 1024 items. 
  40.  *
  41.  *  Note that the maximum comparisons that will ever occur with the merge-sort 
  42.  *  is no more than  n  more than the minimum number possible with the tree 
  43.  *  sort.  
  44.  *
  45.  *  While these numbers look impressive, there is one drawback:  the merge-
  46.  *  sort is heavily weighted toward its worst case, since the merge sort skips 
  47.  *  comparisons only when one list runs out of items more than one item before 
  48.  *  the other.  In practice, the average number of comparisons made by the 
  49.  *  merge-sort is a consistant 96% of the maximum number.  This gives you a very
  50.  *  acurate estimate of the number of comparisons (hence the time it takes) to 
  51.  *  sort a list of a particular size.  Since the maximum value is so close to
  52.  *  the most probable value, you don;t have to worry about pathelogic cases
  53.  *  slowing down your sort routine (for a tree sort, the "pathelogic" case
  54.  *  is a pre-sorted list, which may not be an uncommon case).
  55.  *
  56.  *  In a comparison against the tree sort using random data (the kind the 
  57.  *  tree sort handles best), the merge-sort was found to take 96% of its 
  58.  *  maximum number of sorts, while the tree sort averaged about 38% more than
  59.  *  it's minimum (there was considerably more variation with the tree sort).
  60.  *  Overall, the tree sort was found to take a consitant 25% more comparisons
  61.  *  than the merge-sort on lists of length 300 items to 10000 items.  For
  62.  *  100 items, the difference drops off to about 15%, and for 10 items, the two
  63.  *  sorts are about the same, with the merge-sort comming out a little bit
  64.  *  ahead (one or two comparisons out of an average of 23).
  65.  *
  66.  *  All in all, the merge-sort is an effective, fast, and very useful sort
  67.  *  that compares favorably with other sort algorithms.
  68.  */
  69.  
  70. #include <exec/types.h>
  71.  
  72. #define ADD_TO_NEWLIST(l)   (NewList = (NewList->Next = l))
  73. #define ADD_TO_TOP(i)       {(i)->Next = *CurList; *CurList = i;}
  74. #define ADD_TO_BOTTOM(i)    (CurLast = (CurLast->Next = i))
  75.  
  76. /*
  77.  *  The linked list is a double-linked list (there are pointers to both
  78.  *  the previous and the following item).  The end of the list is marked
  79.  *  by NULL pointers.
  80.  *
  81.  *  The pointers should appear at the top of the structure you intend to
  82.  *  sort, so if you are sorting a linked list of people's names, you might
  83.  *  use a structure like the following in your main program:
  84.  *
  85.  *      struct ListItem
  86.  *      {
  87.  *          struct ListItem *Next;
  88.  *          struct ListItem *Prev;
  89.  *          char FirstName[30];
  90.  *          char MiddleInitial;
  91.  *          char LastName[50]
  92.  *      };
  93.  *
  94.  *  The pointers must be the first fields so that mSort() and mMerge() can
  95.  *  find the pointers without having to know anything about the structure
  96.  *  of the data you are sorting.
  97.  */
  98.  
  99. /*
  100.  *  The #ifndef is so that this module can be #included into the program
  101.  *  that calls mSort(), rather than requiring it to be linked in separately.
  102.  *  To avoid a conflicting definition error, #define NextList to be the
  103.  *  name of the pointer to the previous item as it is declared in your
  104.  *  program (for the example given above, user #define NextList Prev).
  105.  *  be sure that the #define and the struct ListItem declaration both
  106.  *  appear before the #include for this module
  107.  */
  108.  
  109. #ifndef NextList
  110. struct ListItem
  111. {
  112.    struct ListItem *Next;
  113.    struct ListItem *NextList;
  114. };
  115. #endif
  116.  
  117. /*
  118.  *  These are the compare and dispose functions passed to mSort() (see
  119.  *  mSort() for more details), and are assigned to global variables so that
  120.  *  they don't have to be passed to mMerge() every time it is called.
  121.  */
  122.  
  123. static int  (*mCompare)() = NULL;
  124. static void (*mDispose)() = NULL;
  125.  
  126.  
  127. #ifdef FANCYLISTS
  128. /*
  129.  * mInitLists()
  130.  *
  131.  *  This routine converts the original linked list into smaller, separate
  132.  *  lists.  Each of the resulting lists is sorted.  The new lists are built
  133.  *  by taking the first item in the original list as the start of the first
  134.  *  new list, and adding additional items to the top or bottom of this list
  135.  *  until we find an item that can not be added (i.e., it belongs in the
  136.  *  middle of the list somewhere).  This item then becomes the start of
  137.  *  the next new list, and the process is repeated until there are no more
  138.  *  items to add.  The resulting lists are linked into a ring, and then
  139.  *  returned as a linked-list of linked-lists.
  140.  */
  141.  
  142. static struct ListItem *mInitLists(CurItem)
  143. struct ListItem *CurItem;
  144. {
  145.    struct ListItem *FirstList = CurItem;
  146.    struct ListItem *NextItem  = CurItem->Next;
  147.    struct ListItem **CurList  = &FirstList;
  148.    struct ListItem *CurLast   = CurItem;
  149.    int result;
  150.  
  151.    CurLast->Next = NULL;
  152.    while (CurItem = NextItem)
  153.    {
  154.       NextItem = CurItem->Next;
  155.       CurItem->Next = NULL;
  156.       result = (*mCompare)(CurItem,CurLast);
  157.       if (result < 0)
  158.       {
  159. #ifndef TAIL_ONLY
  160.          if (CurLast != *CurList) result = (*mCompare)(CurItem,*CurList);
  161.          if (result == 0 && mDispose) (*mDispose)(CurItem);
  162.          else if (result < 0) ADD_TO_TOP(CurItem)
  163.          else
  164. #endif
  165.          {
  166.             (*CurList)->NextList = CurLast = CurItem;
  167.             CurList = &((*CurList)->NextList);
  168.          }
  169.       } else if (result == 0 && mDispose) (*mDispose)(CurItem);
  170.         else ADD_TO_BOTTOM(CurItem);
  171.    }
  172.    (*CurList)->NextList = FirstList;
  173.    return(FirstList);
  174. }
  175. #endif
  176.  
  177.  
  178. /*
  179.  * mMerge()
  180.  *
  181.  *  combines two sorted linked lists into one sorted linked list, using
  182.  *  the mCompare() function to determine the sorting, and the dispose()
  183.  *  function to remove duplicate values.
  184.  *
  185.  *      list1           a pointer to the first linked list
  186.  *      list2           a pointer to the second linked list
  187.  */
  188.  
  189. static struct ListItem *mMerge(list1,list2)
  190. struct ListItem *list1, *list2;
  191. {
  192.    static struct ListItem TopItem;
  193.    static struct ListItem *NewList, *temp;
  194.    static int result;
  195.  
  196.    TopItem.Next = TopItem.NextList = NULL;
  197.    NewList = &TopItem;
  198.  
  199. /*
  200.  *  While there are still items in each list, compare the top items in the 
  201.  *  lists.  Link the smaller one to the end of the new, combined list, and
  202.  *  pop the item off the top of the old list.  If the top items are equal, 
  203.  *  then add one of them to the new list, and if there is a dispose function,
  204.  *  get rid of the other one, otherwise add the second one into the list
  205.  *  as well.
  206.  *
  207.  *  When one of the lists is exauseted, add any remaining items from 
  208.  *  the other list onto the end of the result list, and return a pointer
  209.  *  to the final, sorted list.
  210.  */
  211.  
  212.    while (list1 != NULL && list2 != NULL)
  213.    {
  214.       result = (*mCompare)(list1,list2);
  215.       if (result < 0)
  216.       {
  217.          ADD_TO_NEWLIST(list1);
  218.          list1 = list1->Next;
  219.       } else if (result > 0) {
  220.          ADD_TO_NEWLIST(list2);
  221.          list2 = list2->Next;
  222.       } else {
  223.          ADD_TO_NEWLIST(list1);
  224.          list1 = list1->Next;
  225.          if (mDispose == NULL)
  226.          {
  227.             ADD_TO_NEWLIST(list2);
  228.             list2 = list2->Next;
  229.          } else {
  230.             temp = list2;
  231.             list2 = list2->Next;
  232.             temp->Next = temp->NextList = NULL;
  233.             (*mDispose)(temp);
  234.          }
  235.       }
  236.    }
  237.    if (list1 != NULL) ADD_TO_NEWLIST(list1);
  238.    else if (list2 != NULL) ADD_TO_NEWLIST(list2);
  239.    return(TopItem.Next);
  240. }
  241.  
  242.  
  243. /*
  244.  *  mSort()
  245.  *
  246.  *  sorts a linked list of items of any sort, using a user-provided comparison
  247.  *  routine.  Duplicate items will be removed if the dispose routine is
  248.  *  provided.  The result list will be a doubly-linked list (pointers go both
  249.  *  forward and backward) that is sorted.  mSort() returns a pointer to
  250.  *  the top of the result list.
  251.  *
  252.  *      CurItem         a pointer to the begining of the original, unsorted
  253.  *                      list.
  254.  *      compare()       a pointer to a function that compares two
  255.  *                      ListItems and returns a negative number if
  256.  *                      the first item is smaller, zero if they are
  257.  *                      equal, and a positive number if the first
  258.  *                      item is larger than the second.  Compare() 
  259.  *                      should take two parameters, the pointers
  260.  *                      to the ListItems that are to be compared.
  261.  *      dispose()       disposes of a duplicate ListItem.  Dispose()
  262.  *                      should accept one parameter, the pointer to
  263.  *                      the ListItem to be removed.  Dispose() should
  264.  *                      free any memory allocated to the ListItem.
  265.  *                      This list item will not appear in the final
  266.  *                      linked list.  If dispose in NULL, then 
  267.  *                      duplicate items are retained in the list.
  268.  */
  269.  
  270. struct ListItem *mSort(CurItem,compare,dispose)
  271. struct ListItem *CurItem;
  272. int (*compare)();
  273. void (*dispose)();
  274. {
  275.    struct ListItem *FirstItem, *NextItem;
  276.    
  277. /*
  278.  *  Put the compare and dispose routines where mMerge() can find them
  279.  */
  280.    mCompare = compare;
  281.    mDispose = dispose;
  282.  
  283.    FirstItem = NULL;
  284.    if (CurItem != NULL)
  285.    {
  286.  
  287.  
  288. #ifdef FANCYLISTS
  289. /*
  290.  *  Separate the initial list into smaller separate lists that are
  291.  *  sorted.  These will be merged below.
  292.  */
  293.      FirstItem = mInitLists(CurItem);
  294. #else
  295. /*
  296.  *  Put each item in the original list into a separate list.  Use the
  297.  *  NextList field to link the individual lists into a list (a linked list
  298.  *  of linked lists).  Link the end of the list to the begining so we get
  299.  *  a ring rather than a list.
  300.  */
  301.       FirstItem = CurItem;
  302.       do
  303.       {
  304.          NextItem = CurItem->Next;
  305.          CurItem->Next = NULL;
  306.          CurItem->NextList = (NextItem != NULL)? NextItem : FirstItem;
  307.          CurItem = NextItem;
  308.       } while (CurItem != NULL);
  309. #endif
  310.  
  311. /*
  312.  *  While there's more than one list left in the ring (i.e., the list 
  313.  *  following the current one is not itself), then merge the current list
  314.  *  with the one following it (keep track of the first list after the ones
  315.  *  we're combining so we can link the result of the merge back into
  316.  *  the ring).  Finally, if there were more than two lists in the ring
  317.  *  (i.e., if the current list is neither equal to the one preceding it nor
  318.  *  equal to the one after the list with which it was combined), then 
  319.  *  link the result list into the ring, otherwise link the result list
  320.  *  to itself (since there were only two lists in the ring, their
  321.  *  merger should leave us with only one).  Move down the ring, so we
  322.  *  can merge the next two lists in the ring.
  323.  */
  324.       while ((CurItem = FirstItem->NextList) != FirstItem)
  325.       {
  326.          NextItem = CurItem->NextList->NextList;
  327.          CurItem = mMerge(CurItem,CurItem->NextList,compare,dispose);
  328.          if (CurItem == FirstItem || CurItem == NextItem)
  329.          {
  330.             CurItem->NextList = CurItem;
  331.          } else {
  332.             FirstItem->NextList = CurItem;
  333.             CurItem->NextList = NextItem;
  334.          }
  335.          FirstItem = CurItem;
  336.       }
  337. /*
  338.  *  When there's only one list left, traverse the list, setting the
  339.  *  reverse pointers so that the list is properly linked both directions.
  340.  */
  341.       FirstItem->NextList = NULL;
  342.       while (CurItem->Next != NULL)
  343.       {
  344.          CurItem->Next->NextList = CurItem;
  345.          CurItem = CurItem->Next;
  346.       }
  347.    }
  348.    return(FirstItem);
  349. }
  350.