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