Return to InsertionSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* An intuitive sort, if not a fast one.  It incrementally builds a sorted 
 * list by considering each element in turn and inserting it in its proper 
 * place among those already sorted.  In the beginning, the first element 
 * constitutes the sorted list.  Then, inserting second element before or 
 * after the first element creates a sorted list length two.  Subsequent 
 * elements are inserted into the growing list.  Each insertion becomes more 
 * costly as the sorted list gets longer since it takes longer to find the 
 * proper place--notice how insertion sort slows down as it gets to the final 
 * elements.  It is an O(n^2) sort, but works well on small data sets and takes 
 * advantage of partially sorted data. 
 *
 * 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 "InsertionSort.h"


@implementation InsertionSort:GenericSort


- init;
{
    [super init];
    sortName = "Insertion Sort";
    sortNum = INSERTION_SORT;
    return self;
}


- sort;
/* There is slight inconsistency in my Insertion Sort algorithm which I should 
 * explain. Typically when you are trying to insert a value into place, you 
 * save the value and keep moving its neighbors up one it until you find where 
 * the value belongs.  You would use a move instruction to put the saved value 
 * in its final place rather than swap it all the way there.  For the purposes 
 * of animation, the swapping looked better, so I do the swaps, but I subtract 
 * a move from Insertion Sort's counter each time, because it is not fair to 
 * charge Insertion Sort for two moves, when the algorithm really only calls 
 * for one.
 * I know this is sort of cheesy, but Sorting In Action is a teaching tool, 
 * and it is very helpful to see this visual animation of what Insertion Sort 
 * is doing.  If you are purist, you could replace this algorithm with one
 * that performs more like a pure Insertion Sort.
 */
{
    int c,d;
    BOOL found;
    
    [super sort];
    fcalls ++;    
    for (c = 1; c < numElements; c++){
    	found = NO;
	d = c-1;
	while ((d >= 0) && !found) {	// move to left until find right place
	    if ([self lessThan:d+1 :d]) { 
	        [self swap:d+1 with:d];	// swap each time (for visual effect)
	        moves--;		// but subtract move to make fair
		d--; 
	    } 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.