home *** CD-ROM | disk | FTP | other *** search
/ Borland Programmer's Resource / Borland_Programmers_Resource_CD_1995.iso / winsock / wvnsc926 / rcs / shellsor.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-19  |  6.1 KB  |  296 lines

  1. head    1.8;
  2. access;
  3. symbols
  4.     V80:1.1
  5.     V76d:1.1;
  6. locks; strict;
  7. comment    @ * @;
  8.  
  9.  
  10. 1.8
  11. date    94.09.03.01.08.03;    author rushing;    state Exp;
  12. branches;
  13. next    1.7;
  14.  
  15. 1.7
  16. date    94.09.02.23.50.14;    author rushing;    state Exp;
  17. branches;
  18. next    1.6;
  19.  
  20. 1.6
  21. date    93.12.08.01.28.38;    author rushing;    state Exp;
  22. branches;
  23. next    1.5;
  24.  
  25. 1.5
  26. date    93.07.08.19.41.06;    author rushing;    state Exp;
  27. branches;
  28. next    1.4;
  29.  
  30. 1.4
  31. date    93.07.06.21.09.09;    author cnolan;    state Exp;
  32. branches;
  33. next    1.3;
  34.  
  35. 1.3
  36. date    93.06.29.20.06.34;    author rushing;    state Exp;
  37. branches;
  38. next    1.2;
  39.  
  40. 1.2
  41. date    93.06.28.17.53.24;    author rushing;    state Exp;
  42. branches;
  43. next    1.1;
  44.  
  45. 1.1
  46. date    93.02.16.20.53.50;    author rushing;    state Exp;
  47. branches;
  48. next    ;
  49.  
  50.  
  51. desc
  52. @winvn version 0.76 placed into RCS
  53. @
  54.  
  55.  
  56. 1.8
  57. log
  58. @define huge away for win32
  59. @
  60. text
  61. @
  62. /*
  63.  *
  64.  * $Id: shellsor.c 1.7 1994/09/02 23:50:14 rushing Exp rushing $
  65.  * $Log: shellsor.c $
  66.  * Revision 1.7  1994/09/02  23:50:14  rushing
  67.  * shellsort is now huge
  68.  *
  69.  * Revision 1.6  1993/12/08  01:28:38  rushing
  70.  * new version box and cr lf consistency
  71.  *
  72.  * Revision 1.5  1993/07/08  19:41:06  rushing
  73.  * fixed unsigned bug again.  strange.
  74.  *
  75.  * Revision 1.4  1993/07/06  21:09:09  cnolan
  76.  * win32 support
  77.  *
  78.  * Revision 1.2  1993/06/28  17:53:24  rushing
  79.  * fixed compiler warnings
  80.  *
  81.  * Revision 1.1  1993/02/16  20:53:50  rushing
  82.  * Initial revision
  83.  *
  84.  *
  85.  */
  86.  
  87. /* Shellsort is a variation on Insertion Sort that is virtually unbeatable
  88.  * on small data sets.  Insertion Sort is slow because it only exchanges
  89.  * adjacent elements.  Shellsort circumvents this by allowing the exchange
  90.  * of elements that are farther apart.  It works by first performing Insertion
  91.  * Sort on subsets of the data.  For example, Shellsort might first sort
  92.  * the set of elements 1, 6, 11, 16... relative to each other--the effect
  93.  * is that the elements in that subset are moved much closer to their final
  94.  * positions.  At first the sets are wide-spread, perhaps every fortieth
  95.  * element.  Then it repeats using a tighter set, perhaps every fourteenth
  96.  * element, then every fourth element.  Each of these passes is much cheaper
  97.  * than a traditional Insertion Sort pass.  The effect of the passes is that
  98.  * the data set is mutated to be in "almost sorted" order.  The final insertion
  99.  * sort pass can then go very quickly because insertion sort does very well on
  100.  * almost sorted data.  In other words, at first the elements take large leaps
  101.  * to the general location they belong and successively smaller steps move the
  102.  * element to its precise place. I call this algorithm "inscrutable sort"
  103.  * because even after having coded the algorithm, I still have trouble
  104.  * following the animation.  No one has been able to analyze this algorithm
  105.  * rigorously; the functional form of the running time is conjectured to be
  106.  * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general
  107.  * purpose sort since it has excellent performance and the code you must write
  108.  * is only slightly more complex than Insertion Sort.
  109.  *
  110.  * Author: Julie Zelenski, NeXT Developer Support
  111.  * You may freely copy, distribute and reuse the code in this example.
  112.  * NeXT disclaims any warranty of any kind, expressed or implied, as to
  113.  * its fitness for any particular use.      qsort
  114.  */
  115.  
  116. #ifdef WIN32
  117. #include <windef.h>
  118. #endif
  119.  
  120. #include <stdio.h>
  121. #include <string.h>
  122.  
  123. #ifdef WIN32
  124.   #define __far far
  125.   #define huge far
  126.   #define       __near near
  127. #endif
  128.  
  129.  
  130. #define memSwap(a,b,unused) tmp = *(char huge * huge *)(a); \
  131.   *(char huge * huge *)(a) = *(char huge * huge *)(b); *(char huge * huge *)(b) = tmp;
  132.  
  133. void
  134. ShellSort (void huge * huge * base,
  135.        size_t nElements,
  136.        size_t width,
  137.        int (*compare) (void const huge *elem1, void const huge * elem2))
  138. {
  139. #define STRIDE_FACTOR 3
  140.   unsigned int c, stride;
  141.   int d;
  142.   char far *tmp;
  143.   int found;
  144.  
  145.   stride = 1;
  146.   while (stride <= nElements)
  147.     stride = stride * STRIDE_FACTOR + 1;
  148.  
  149.   while (stride > (STRIDE_FACTOR - 1))
  150.     {
  151.       stride = stride / STRIDE_FACTOR;
  152.       for (c = stride; c < nElements; c++)
  153.     {
  154.       found = 0;
  155.       d = c - stride;
  156.       while ((d >= 0) && !found)
  157.         {
  158.           if (compare ((char huge *) base + (d + stride) * width, (char huge *) base + d * width) < 0)
  159.         {
  160.           memSwap ((char huge *) base + (d + stride) * width, (char huge *) base + d * width, width);
  161.           d -= stride;
  162.         }
  163.           else
  164.         {
  165.           found = 1;
  166.         }
  167.         }
  168.     }
  169.     }
  170. }
  171. @
  172.  
  173.  
  174. 1.7
  175. log
  176. @shellsort is now huge
  177. @
  178. text
  179. @d4 1
  180. a4 1
  181.  * $Id: shellsor.c 1.6 1993/12/08 01:28:38 rushing Exp rushing $
  182. d6 3
  183. d64 3
  184. a66 1
  185. #  define __far far
  186. d68 1
  187. @
  188.  
  189.  
  190. 1.6
  191. log
  192. @new version box and cr lf consistency
  193. @
  194. text
  195. @d4 1
  196. a4 1
  197.  * $Id: shellsor.c 1.5 1993/07/08 19:41:06 rushing Exp rushing $
  198. d6 3
  199. d64 2
  200. a65 3
  201. #define memSwap(a,b,unused) tmp = *(char far * far *)(a); \
  202.   *(char far * far *)(a) = *(char far * far *)(b); *(char far * far *)(b) = tmp;
  203.  
  204. d67 5
  205. a71 6
  206. void __far
  207. ShellSort (base, nElements, width, compare)
  208.      void far *base;
  209.      size_t nElements;
  210.      size_t width;
  211.      int (__far * compare) (void const far * elem1, void const far * elem2);
  212. d92 1
  213. a92 1
  214.           if (compare ((char far *) base + (d + stride) * width, (char far *) base + d * width) < 0)
  215. d94 1
  216. a94 1
  217.           memSwap ((char far *) base + (d + stride) * width, (char far *) base + d * width, width);
  218. @
  219.  
  220.  
  221. 1.5
  222. log
  223. @fixed unsigned bug again.  strange.
  224. @
  225. text
  226. @d1 1
  227. d4 1
  228. a4 1
  229.  * $Id: shellsor.c 1.4 1993/07/06 21:09:09 cnolan Exp rushing $
  230. d6 3
  231. @
  232.  
  233.  
  234. 1.4
  235. log
  236. @win32 support
  237. @
  238. text
  239. @d3 1
  240. a3 1
  241.  * $Id: shellsor.c 1.2 1993/06/28 17:53:24 rushing Exp $
  242. d5 3
  243. d69 2
  244. a70 1
  245.   unsigned int c, d, stride;
  246. @
  247.  
  248.  
  249. 1.3
  250. log
  251. @fixed unsigned/signed bug
  252. .,
  253. @
  254. text
  255. @d3 1
  256. a3 1
  257.  * $Id: shellsor.c 1.2 1993/06/28 17:53:24 rushing Exp rushing $
  258. d43 4
  259. d50 4
  260. d66 1
  261. a66 2
  262.   unsigned int c, stride;
  263.   int d;
  264. @
  265.  
  266.  
  267. 1.2
  268. log
  269. @fixed compiler warnings
  270. @
  271. text
  272. @d3 1
  273. a3 1
  274.  * $Id: shellsor.c 1.1 1993/02/16 20:53:50 rushing Exp rushing $
  275. d5 3
  276. d58 2
  277. a59 1
  278.   unsigned int c, d, stride;
  279. @
  280.  
  281.  
  282. 1.1
  283. log
  284. @Initial revision
  285. @
  286. text
  287. @d3 4
  288. a6 2
  289.  * $Id$
  290.  * $Log$
  291. d8 1
  292. d55 1
  293. a55 1
  294.   int c, d, stride;
  295. @
  296.