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