Return to BubbleSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* A classic sort, although not a particularly efficient one.  Its basic 
 * strategy is to begin at top and look at the first two elements and move 
 * the larger of the two down.  Then it looks at the the second and third 
 * elements, moves the larger down.  It continues like this, "bubbling" the 
 * largest element down to the very bottom. Then it returns to the top to do 
 * it all over again.  It finishes when no more elements need to be exchanged. 
 * It is the poorest performer of the O(n^2) sorts, although it does improve 
 * somewhat on partially sorted data.  As Don Knuth said, "In short, the 
 * bubble sort seems to have nothing to recommend it, except a catchy name 
 * and the fact that it lead to some interesting theoretical problems."  
 * If you are ever tempted to use Bubble Sort, wait for the feeling to pass, 
 * and then use Insertion Sort which is marginally faster and easier to write.
 *
 * Author: Julie Zelenski, NeXT Developer Support
 * You may freely copy, distribute and reuse the code in this example.  
 * NeXT disclaims any warranty of any kind, expressed or implied, as to 
 * its fitness for any particular use.
 */
 
 
#import "BubbleSort.h"

@implementation BubbleSort:GenericSort


- init;
{
    [super init];
    sortName = "Bubble Sort";
    sortNum = BUBBLE_SORT;
    return self;
}


- sort;
{
    int a,bound;
    BOOL sorted = NO;
    
    [super sort];
    fcalls++;
    bound = numElements - 1;		
    while (sorted == NO) {  // while exchanges are still necessary
       	sorted = YES;
        for (a = 0;a < bound; a++) {  
	    if ([self lessThan:a+1 :a]) { // if less than your left neighbor
	        sorted = NO;    
	        [self swap:a+1 with:a];   // swap with neighbor
	    }
	}
	bound--;
    }
    [self sortDone];
    return self;
}

@end

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