home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Examples / AppKit / SortingInAction / ShellSort.m < prev    next >
Encoding:
Text File  |  1990-10-09  |  3.1 KB  |  82 lines
  1.  
  2. /* Shellsort is a variation on Insertion Sort that is virtually unbeatable 
  3.  * on small data sets.  Insertion Sort is slow because it only exchanges 
  4.  * adjacent elements.  Shellsort circumvents this by allowing the exchange 
  5.  * of elements that are farther apart.  It works by first performing Insertion 
  6.  * Sort on subsets of the data.  For example, Shellsort might first sort 
  7.  * the set of elements 1, 6, 11, 16... relative to each other--the effect 
  8.  * is that the elements in that subset are moved much closer to their final 
  9.  * positions.  At first the sets are wide-spread, perhaps every fortieth 
  10.  * element.  Then it repeats using a tighter set, perhaps every fourteenth 
  11.  * element, then every fourth element.  Each of these passes is much cheaper 
  12.  * than a traditional Insertion Sort pass.  The effect of the passes is that 
  13.  * the data set is mutated to be in "almost sorted" order.  The final insertion 
  14.  * sort pass can then go very quickly because insertion sort does very well on 
  15.  * almost sorted data.  In other words, at first the elements take large leaps 
  16.  * to the general location they belong and successively smaller steps move the 
  17.  * element to its precise place. I call this algorithm "inscrutable sort" 
  18.  * because even after having coded the algorithm, I still have trouble 
  19.  * following the animation.  No one has been able to analyze this algorithm 
  20.  * rigorously; the functional form of the running time is conjectured to be 
  21.  * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general 
  22.  * purpose sort since it has excellent performance and the code you must write 
  23.  * is only slightly more complex than Insertion Sort.
  24.  *
  25.  * Author: Julie Zelenski, NeXT Developer Support
  26.  * You may freely copy, distribute and reuse the code in this example.  
  27.  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
  28.  * its fitness for any particular use.
  29.  */
  30.  
  31.  
  32. #import "ShellSort.h"
  33.  
  34.  
  35. @implementation ShellSort:GenericSort
  36.  
  37.  
  38. - init;
  39. {
  40.     [super init];
  41.     sortName = "Shellsort";
  42.     sortNum = SHELL_SORT;
  43.     return self;
  44. }
  45.  
  46. - sort;
  47. /* Because Shellsort is a variation on Insertion Sort, it has the same 
  48.  * inconsistency that I noted in the InsertionSort class.  Notice where I 
  49.  * subtract a move to compensate for calling a swap for visual purposes.
  50.  */
  51. {
  52. #define STRIDE_FACTOR 3     // good value for stride factor is not well-understood
  53.                 // 3 is a fairly good choice (Sedgewick)
  54.     int c,d, stride;
  55.     BOOL found;
  56.  
  57.     [super sort];
  58.     fcalls++; 
  59.     stride = 1;
  60.     while (stride <= numElements)
  61.       stride = stride*STRIDE_FACTOR +1;
  62.     
  63.     while (stride>(STRIDE_FACTOR-1)) { // loop to sort for each value of stride
  64.         stride = stride / STRIDE_FACTOR;
  65.     for (c = stride; c < numElements; c++){
  66.         found = NO;
  67.         d = c-stride;
  68.         while ((d >= 0) && !found) { // move to left until correct place
  69.             if ([self lessThan:d+stride :d]) {
  70.             [self swap:d+stride with:d];//swap each time(visual effect)
  71.             moves--;            // subtract move to make fair
  72.             d -= stride;        // jump by stride factor
  73.         } else
  74.             found = YES;
  75.         }
  76.     }
  77.     }
  78.     [self sortDone];
  79.     return self;
  80. }
  81.     
  82. @end