Return to BubbleSort.m CVS log

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

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

1.1       root        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:     
                     41:     [super sort];
                     42:     fcalls++;
                     43:     bound = numElements - 1;           
                     44:     while (sorted == NO) {  // while exchanges are still necessary
                     45:                sorted = YES;
                     46:         for (a = 0;a < bound; a++) {  
                     47:            if ([self lessThan:a+1 :a]) { // if less than your left neighbor
                     48:                sorted = NO;    
                     49:                [self swap:a+1 with:a];   // swap with neighbor
                     50:            }
                     51:        }
                     52:        bound--;
                     53:     }
                     54:     [self sortDone];
                     55:     return self;
                     56: }
                     57: 
                     58: @end

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