home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.0 / NeXTSTEP3.0.iso / NextDeveloper / Examples / AppKit / SortingInAction / QuickSort.m < prev    next >
Encoding:
Text File  |  1990-10-09  |  2.3 KB  |  77 lines
  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 UPthat 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