Return to InsertionSort.m CVS log

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

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

1.1       root        1: 
                      2: /* An intuitive sort, if not a fast one.  It incrementally builds a sorted 
                      3:  * list by considering each element in turn and inserting it in its proper 
                      4:  * place among those already sorted.  In the beginning, the first element 
                      5:  * constitutes the sorted list.  Then, inserting second element before or 
                      6:  * after the first element creates a sorted list length two.  Subsequent 
                      7:  * elements are inserted into the growing list.  Each insertion becomes more 
                      8:  * costly as the sorted list gets longer since it takes longer to find the 
                      9:  * proper place--notice how insertion sort slows down as it gets to the final 
                     10:  * elements.  It is an O(n^2) sort, but works well on small data sets and takes 
                     11:  * advantage of partially sorted data. 
                     12:  *
                     13:  * Author: Julie Zelenski, NeXT Developer Support
                     14:  * You may freely copy, distribute and reuse the code in this example.  
                     15:  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
                     16:  * its fitness for any particular use.
                     17:  */
                     18:  
                     19:  
                     20: #import "InsertionSort.h"
                     21: 
                     22: 
                     23: @implementation InsertionSort:GenericSort
                     24: 
                     25: 
                     26: - init;
                     27: {
                     28:     [super init];
                     29:     sortName = "Insertion Sort";
                     30:     sortNum = INSERTION_SORT;
                     31:     return self;
                     32: }
                     33: 
                     34: 
                     35: - sort;
                     36: /* There is slight inconsistency in my Insertion Sort algorithm which I should 
                     37:  * explain. Typically when you are trying to insert a value into place, you 
                     38:  * save the value and keep moving its neighbors up one it until you find where 
                     39:  * the value belongs.  You would use a move instruction to put the saved value 
                     40:  * in its final place rather than swap it all the way there.  For the purposes 
                     41:  * of animation, the swapping looked better, so I do the swaps, but I subtract 
                     42:  * a move from Insertion Sort's counter each time, because it is not fair to 
                     43:  * charge Insertion Sort for two moves, when the algorithm really only calls 
                     44:  * for one.
                     45:  * I know this is sort of cheesy, but Sorting In Action is a teaching tool, 
                     46:  * and it is very helpful to see this visual animation of what Insertion Sort 
                     47:  * is doing.  If you are purist, you could replace this algorithm with one
                     48:  * that performs more like a pure Insertion Sort.
                     49:  */
                     50: {
                     51:     int c,d;
                     52:     BOOL found;
                     53:     
                     54:     [super sort];
                     55:     fcalls ++;    
                     56:     for (c = 1; c < numElements; c++){
                     57:        found = NO;
                     58:        d = c-1;
                     59:        while ((d >= 0) && !found) {    // move to left until find right place
                     60:            if ([self lessThan:d+1 :d]) { 
                     61:                [self swap:d+1 with:d]; // swap each time (for visual effect)
                     62:                moves--;                // but subtract move to make fair
                     63:                d--; 
                     64:            } else
                     65:                found = YES;
                     66:        }
                     67:     }
                     68:     [self sortDone];
                     69:     return self;
                     70: }
                     71: 
                     72: @end

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