home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part02 / insert_sort.c < prev    next >
C/C++ Source or Header  |  1992-12-18  |  3KB  |  126 lines
  1.  
  2. /* 
  3.  
  4. NAME
  5.   insertion sort 
  6.  
  7. DESCRIPTION
  8.  
  9.   Sorts by inserting each successive record into its proper place in
  10.   the preceeding, already sorted records.   Perform a binary search on
  11.   the preceeding records to find where to insert the current record,
  12.   then shift all the records over to make room in the right place.
  13.  
  14. AUTHORSHIP
  15.  
  16.   This is properly called the binary insertion sort and credit is
  17.   given for first publication to John Mauchly, 1946.
  18.  
  19. REFERENCES
  20.  
  21.   Knuth, Art of Computer Programming Vol 3, page 83.
  22.  
  23. COMPLEXITY
  24.  
  25.   O(n log n) comparisons 
  26.   O(0.25 * n^2) memory operations
  27.   Iterative.
  28.  
  29. COPYRIGHT
  30.  
  31.   Copyright 1992 Michael Lee.
  32.  
  33.   (1) Permission to use, copy, distribute, and make changes is granted
  34.   providing that (a) that you do so without charging anyone a fee and
  35.   (b) this copyright notice must be included verbatim in all copies and 
  36.   distributions.  
  37.  
  38.   (2) There is no warranty for this program, to the extent permitted by
  39.   applicable law.  This program is provided "AS IS" without warranty of
  40.   any kind, either expressed or implied, including, but not limited to,
  41.   the implied warranties of merchantability and fitness for a particular 
  42.   purpose.  The entire risk as to the quality and performance of this 
  43.   program is with the user.  Should this program prove defective, the 
  44.   user assumes the cost of all necessary servicing, repair or correction.
  45.  
  46.   (3) In no event unless required by applicable law will the copyright
  47.   holder be liable to the user for damages, including any general,
  48.   special, incidental or consequential damages arising out of the use
  49.   or inability to use this program (including but not limited to loss of
  50.   data or data being rendered inaccurate or losses sustained by the
  51.   user or third parties or a failure of this program to operate with any
  52.   other programs), even if such holder or third party has been advised
  53.   of the possibility of such damages.
  54.  
  55.   (4) Object code produced by a compiler from this code may be 
  56.   incorporated into commercial products without being subject to 
  57.   restrictions (1)(a) or (1)(b).
  58.  
  59. */
  60.  
  61. #include <stdio.h>
  62. #include <malloc.h>
  63. #include <memory.h>
  64. #include <string.h>
  65. #include <assert.h>
  66.  
  67. #include "sorting.h"
  68.  
  69. int insertion_sort(base, nelem, width, cmpr_func)
  70.   char * base;
  71.   int nelem;
  72.   int width;
  73.   int (*cmpr_func)();
  74. {
  75.   int i, top, middle, bottom;
  76.   int found, test;
  77.   char * temp;
  78.  
  79.   temp = malloc(width);
  80.   assert(temp != NULL);
  81.  
  82.   for (i = 1; i < nelem; i++)
  83.   {
  84.     /* binary search looking for place between base[0] and base[i-1] where
  85.        you can insert base[i] into in order. */
  86.  
  87.     bottom = 0;
  88.     top = i-1;
  89.     middle = 0;
  90.     found = 0;
  91.  
  92.     while (top >= bottom && ! found)
  93.     {
  94.       middle = (top+bottom) / 2;
  95.       test = (*cmpr_func)(base+middle*width, base+i*width);
  96.  
  97.       if (test > 0)
  98.         top = middle - 1;
  99.       else if (test < 0)
  100.       {
  101.         middle ++;
  102.         bottom = middle;
  103.       }
  104.       else
  105.       {
  106.         middle ++;
  107.         found = 1;
  108.       }
  109.     }
  110.  
  111.     /* make room at base[middle] for base[i] */
  112.  
  113.     if (i != middle)
  114.     {
  115.       memcpy(temp, base+i*width, width);
  116.       memmove(base+middle*width+width, base+middle*width, (i-middle)*width);
  117.       memcpy(base+middle*width, temp, width);
  118.     }
  119.   }
  120.  
  121.   if (temp != NULL) free(temp);
  122.  
  123.   return 0;
  124.  
  125. }
  126.