Return to ShellSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* Shellsort is a variation on Insertion Sort that is virtually unbeatable 
 * on small data sets.  Insertion Sort is slow because it only exchanges 
 * adjacent elements.  Shellsort circumvents this by allowing the exchange 
 * of elements that are farther apart.  It works by first performing Insertion 
 * Sort on subsets of the data.  For example, Shellsort might first sort 
 * the set of elements 1, 6, 11, 16... relative to each other--the effect 
 * is that the elements in that subset are moved much closer to their final 
 * positions.  At first the sets are wide-spread, perhaps every fortieth 
 * element.  Then it repeats using a tighter set, perhaps every fourteenth 
 * element, then every fourth element.  Each of these passes is much cheaper 
 * than a traditional Insertion Sort pass.  The effect of the passes is that 
 * the data set is mutated to be in "almost sorted" order.  The final insertion 
 * sort pass can then go very quickly because insertion sort does very well on 
 * almost sorted data.  In other words, at first the elements take large leaps 
 * to the general location they belong and successively smaller steps move the 
 * element to its precise place. I call this algorithm "inscrutable sort" 
 * because even after having coded the algorithm, I still have trouble 
 * following the animation.  No one has been able to analyze this algorithm 
 * rigorously; the functional form of the running time is conjectured to be 
 * O(N^1.25).  Shellsort may be a bit mysterious, but it is an good general 
 * purpose sort since it has excellent performance and the code you must write 
 * is only slightly more complex than Insertion Sort.
 *
 * Author: Julie Zelenski, NeXT Developer Support
 * You may freely copy, distribute and reuse the code in this example.  
 * NeXT disclaims any warranty of any kind, expressed or implied, as to 
 * its fitness for any particular use.
 */
 
 
#import "ShellSort.h"


@implementation ShellSort:GenericSort


- init;
{
    [super init];
    sortName = "Shellsort";
    sortNum = SHELL_SORT;
    return self;
}

- sort;
/* Because Shellsort is a variation on Insertion Sort, it has the same 
 * inconsistency that I noted in the InsertionSort class.  Notice where I 
 * subtract a move to compensate for calling a swap for visual purposes.
 */
{
#define STRIDE_FACTOR 3 	// good value for stride factor is not well-understood
				// 3 is a fairly good choice (Sedgewick)
    int c,d, stride;
    BOOL found;

    [super sort];
    fcalls++; 
    stride = 1;
    while (stride <= numElements)
      stride = stride*STRIDE_FACTOR +1;
    
    while (stride>(STRIDE_FACTOR-1)) { // loop to sort for each value of stride
    	stride = stride / STRIDE_FACTOR;
	for (c = stride; c < numElements; c++){
	    found = NO;
	    d = c-stride;
	    while ((d >= 0) && !found) { // move to left until correct place
	        if ([self lessThan:d+stride :d]) {
		    [self swap:d+stride with:d];//swap each time(visual effect)
		    moves--;			// subtract move to make fair
		    d -= stride;		// jump by stride factor
		} else
		    found = YES;
	    }
	}
    }
    [self sortDone];
    return self;
}
	
@end

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