Return to QuickSort.m CVS log

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

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

1.1       root        1: 
                      2: /* True to its name, this sort is fast, but it is not without its faults.   
                      3:  * It works by partitioning a data set into two parts and then recursively 
                      4:  * sorting the parts.  It divides the data by choosing a pivot value and 
                      5:  * moving all elements less than the pivot into one partition, all elements 
                      6:  * greater than the pivot go to the other.  Each of the partitions are split 
                      7:  * again with a new pivot, and following the magic trail of recursion it 
                      8:  * arrives at a sorted data set.  It is fast, even with the overhead of 
                      9:  * recursion.  However, with a poor pivot choice, it can slow down enormously. 
                     10:  * A poor pivot choice is one that divides the data lopsidedly instead of 
                     11:  * creating two fairly equal partitions.  For this reason, Quicksort works 
                     12:  * particularly poorly on data that is already sorted.  Already sorted data 
                     13:  * is, in fact, its worst case at O(n^2) whereas its average case is O(nlogn).
                     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 "QuickSort.h"
                     23: 
                     24: 
                     25: @implementation QuickSort:GenericSort
                     26: 
                     27: - init;
                     28: {
                     29:     [super init];
                     30:     sortName = "Quicksort";
                     31:     sortNum = QUICK_SORT;
                     32:     return self;
                     33: }
                     34: 
                     35: - (int)partition:(int)begin to:(int)end
                     36: {
                     37:     int left, pivot, right;
                     38:     
                     39:     fcalls++;
                     40:     left = begin;
                     41:     right = end;
                     42:     while (left < right) {
                     43:        while ([self lessThan:begin :right]) 
                     44:            right--;    // move to find one that doesn't belong on right side
                     45:        while ((left < right) && (![self lessThan:begin :left])) 
                     46:            left++;     // move to find one that doesn't belong on left side
                     47:        if (left < right)       
                     48:            [self swap:right with:left];        // swap the two elements
                     49:     }
                     50:     pivot = right;
                     51:     [self swap:pivot with:begin];      // move the pivot to the middle
                     52:     return pivot;
                     53: }
                     54:                
                     55: - quicksort:(int)begin to:(int)end
                     56: {    
                     57:     int pivot;
                     58:     
                     59:     fcalls++;
                     60:     if (begin < end) {
                     61:        pivot = [self partition:begin to:end];  // divide into two partitions
                     62:        [self quicksort:begin to:(pivot-1)];    // sort first partition
                     63:        [self quicksort:(pivot+1) to:end];      // sort second partition
                     64:     }
                     65:     return self;
                     66: }
                     67: 
                     68: 
                     69: - sort
                     70: {
                     71:     [super sort];
                     72:     [self quicksort:0 to:(numElements -1)];
                     73:     [self sortDone];
                     74:     return self;
                     75: }
                     76: 
                     77: @end

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