Return to QuickSort.m CVS log

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

Sample Programs from NeXSTEP 3.3

/* True to its name, this sort is fast, but it is not without its faults.   
 * It works by partitioning a data set into two parts and then recursively 
 * sorting the parts.  It divides the data by choosing a pivot value and 
 * moving all elements less than the pivot into one partition, all elements 
 * greater than the pivot go to the other.  Each of the partitions are split 
 * again with a new pivot, and following the magic trail of recursion it 
 * arrives at a sorted data set.  It is fast, even with the overhead of 
 * recursion.  However, with a poor pivot choice, it can slow down enormously. 
 * A poor pivot choice is one that divides the data lopsidedly instead of 
 * creating two fairly equal partitions.  For this reason, Quicksort works 
 * particularly poorly on data that is already sorted.  Already sorted data 
 * is, in fact, its worst case at O(n^2) whereas its average case is O(nlogn).
 *
 * 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 "QuickSort.h"


@implementation QuickSort:GenericSort

- init;
{
    [super init];
    sortName = "Quicksort";
    sortNum = QUICK_SORT;
    return self;
}

- (int)partition:(int)begin to:(int)end
{
    int left, pivot, right;
    
    fcalls++;
    left = begin;
    right = end;
    while (left < right) {
      	while ([self lessThan:begin :right]) 
	    right--;	// move to find one that doesn't belong on right side
	while ((left < right) && (![self lessThan:begin :left])) 
	    left++;	// move to find one that doesn't belong on left side
	if (left < right) 	
	    [self swap:right with:left];	// swap the two elements
    }
    pivot = right;
    [self swap:pivot with:begin];	// move the pivot to the middle
    return pivot;
}
	        
- quicksort:(int)begin to:(int)end
{    
    int pivot;
    
    fcalls++;
    if (begin < end) {
      	pivot = [self partition:begin to:end];	// divide into two partitions
	[self quicksort:begin to:(pivot-1)];	// sort first partition
	[self quicksort:(pivot+1) to:end];	// sort second partition
    }
    return self;
}


- sort
{
    [super sort];
    [self quicksort:0 to:(numElements -1)];
    [self sortDone];
    return self;
}

@end

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