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     ! 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.