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