home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume34 / flogger / part02 / shell_sort.c < prev    next >
C/C++ Source or Header  |  1992-12-18  |  3KB  |  99 lines
  1.  
  2. /*
  3.  
  4. NAME
  5.   shell sort 
  6.  
  7. DESCRIPTION
  8.  
  9.   An exhange sort algorithm which exchanges over larger distances
  10.   than bubble sort, thus reducing the number of exchanges needed.
  11.  
  12. AUTHORSHIP
  13.  
  14.   D. L. Shell
  15.  
  16. REFERENCES
  17.  
  18.   D. L. Shell, CACM 2, July 1959
  19.   Kernighan & Ritchie, C Programming Language, Second Edition, pg 62
  20.   Knuth, Art of Computer Programming Vol 3, pg 84-95
  21.  
  22. COMPLEXITY
  23.  
  24.   I'm not exactly sure, but I think it's O(N^1.5) 
  25.   Iterative.
  26.  
  27. COPYRIGHT
  28.  
  29.   Copyright 1992 Michael Lee.
  30.  
  31.   (1) Permission to use, copy, distribute, and make changes is granted
  32.   providing that (a) that you do so without charging anyone a fee and
  33.   (b) this copyright notice must be included verbatim in all copies and 
  34.   distributions.  
  35.  
  36.   (2) There is no warranty for this program, to the extent permitted by
  37.   applicable law.  This program is provided "AS IS" without warranty of
  38.   any kind, either expressed or implied, including, but not limited to,
  39.   the implied warranties of merchantability and fitness for a particular 
  40.   purpose.  The entire risk as to the quality and performance of this 
  41.   program is with the user.  Should this program prove defective, the 
  42.   user assumes the cost of all necessary servicing, repair or correction.
  43.  
  44.   (3) In no event unless required by applicable law will the copyright
  45.   holder be liable to the user for damages, including any general,
  46.   special, incidental or consequential damages arising out of the use
  47.   or inability to use this program (including but not limited to loss of
  48.   data or data being rendered inaccurate or losses sustained by the
  49.   user or third parties or a failure of this program to operate with any
  50.   other programs), even if such holder or third party has been advised
  51.   of the possibility of such damages.
  52.  
  53.   (4) Object code produced by a compiler from this code may be 
  54.   incorporated into commercial products without being subject to 
  55.   restrictions (1)(a) or (1)(b).
  56.  
  57. */
  58.  
  59. #include <stdio.h>
  60. #include <malloc.h>
  61. #include <memory.h>
  62. #include <string.h>
  63. #include <assert.h>
  64.  
  65. #include "sorting.h"
  66.  
  67. int shell_sort(base, nelem, width, cmpr_func)
  68.   char * base;
  69.   int nelem;
  70.   int width;
  71.   int (*cmpr_func)();
  72. {
  73.   int gap, i, j;
  74.   char * temp;
  75.  
  76.   temp = malloc(width);
  77.   assert(temp != NULL);
  78.  
  79.   for (gap = nelem / 2; gap > 0; gap /= 2)
  80.   {
  81.     for (i = gap; i < nelem; i++)
  82.     {
  83.       for (j = i-gap; 
  84.            j >=0 && (*cmpr_func)(base+j*width, base+(j+gap)*width) > 0;
  85.            j -= gap)
  86.       {
  87.         memcpy(temp, base+j*width, width);
  88.         memcpy(base+j*width, base+(j+gap)*width, width);
  89.         memcpy(base+(j+gap)*width, temp, width);
  90.       }
  91.     }
  92.   }
  93.  
  94.   if (temp != NULL) free(temp);
  95.  
  96.   return 0;
  97.  
  98. }
  99.