home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.0 / NeXTSTEP3.0.iso / NextDeveloper / Examples / AppKit / SortingInAction / InsertionSort.m < prev    next >
Encoding:
Text File  |  1990-10-09  |  2.5 KB  |  72 lines
  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 tU@ 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