Return to ShellSort.m CVS log

Up to [NeXTSTEP 3.3 examples] / Examples / AppKit / SortingInAction

Annotation of Examples/AppKit/SortingInAction/ShellSort.m, revision 1.1.1.1

1.1       root        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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.