home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.0 / NeXTSTEP3.0.iso / NextDeveloper / Examples / AppKit / SortingInAction / BubbleSort.m < prev    next >
Encoding:
Text File  |  1990-10-09  |  1.8 KB  |  57 lines
  1.  
  2. /* A classic sort, although not a particularly efficient one.  Its basic 
  3.  * strategy is to begin at top and look at the first two elements and move 
  4.  * the larger of the two down.  Then it looks at the the second and third 
  5.  * elements, moves the larger down.  It continues like this, "bubbling" the 
  6.  * largest element down to the very bottom. Then it returns to the top to do 
  7.  * it all over again.  It finishes when no more elements need to be exchanged. 
  8.  * It is the poorest performer of the O(n^2) sorts, although it does improve 
  9.  * somewhat on partially sorted data.  As Don Knuth said, "In short, the 
  10.  * bubble sort seems to have nothing to recommend it, except a catchy name 
  11.  * and the fact that it lead to some interesting theoretical problems."  
  12.  * If you are ever tempted to use Bubble Sort, wait for the feeling to pass, 
  13.  * and then use Insertion Sort which is marginally faster and easier to write.
  14.  *
  15.  * Author: Julie Zelenski, NeXT Developer Support
  16.  * You may freely copy, distribute and reuse the code in this example.  
  17.  * NeXT disclaims any warranty of any kind, expressed or implied, as to 
  18.  * its fitness for any particular use.
  19.  */
  20.  
  21.  
  22. #import "BubbleSort.h"
  23.  
  24. @implementation BubbleSort:GenericSort
  25.  
  26.  
  27. - init;
  28. {
  29.     [super init];
  30.     sortName = "Bubble Sort";
  31.     sortNum = BUBBLE_SORT;
  32.     return self;
  33. }
  34.  
  35.  
  36. - sort;
  37. {
  38.     int a,bound;
  39.     BOOL sorted = NO;
  40.   U9   [super sort];
  41.     fcalls++;
  42.     bound = numElements - 1;        
  43.     while (sorted == NO) {  // while exchanges are still necessary
  44.            sorted = YES;
  45.         for (a = 0;a < bound; a++) {  
  46.         if ([self lessThan:a+1 :a]) { // if less than your left neighbor
  47.             sorted = NO;    
  48.             [self swap:a+1 with:a];   // swap with neighbor
  49.         }
  50.     }
  51.     bound--;
  52.     }
  53.     [self sortDone];
  54.     return self;
  55. }
  56.  
  57. @end