lect40a-quicksort
sorting in prolog
and quicksort in several langauges

    %% From the end of lecture yesterday, here is the solution:
    
    /*  [+,+,-]   
      remove(Itm,L,L1): L1 = L, but L1 has one copy of Itm removed.
        (Note that Itm *must* occur in L, to satisfy this.)
    */
    remove(F,[F|L1],L1).
    remove(F,[G|L1],[G|L2]) :- remove(F,L1,L2).
    
    
    
    %%%%%%%%%%%%%%
    % Sorting:
    % We'll just provide the 'spec' for sorting:
    % L2 is a sorted version of L1 if:
    %  - L1 is a permutation (re-arrangement) of L2, and
    %  - L2 is in ascending order (er, non-decreasing).
    
    scrapSort(L1,L2) :- permutation(L1,L2), nondecreasing(L2).
     
    
    % Here're the helper functions:
    %
    nondecreasing([]).
    nondecreasing([_]).
    nondecreasing([F,S|R]) :- F=<S, nondecreasing([S|R]).
    
    /* permutation(L1,L2): L2 is a permutation of L1 */
    permutation([],[]).
    permutation(X,[F|R]) :- remove(F,X,Z), permutation(Z,R).
    %
    % `permutation` is actually kinda tricky to come up with.
    % A couple of false-starts (and explanations) are at:
    %   http://www.radford.edu/~itec380/2009fall-ibarland/Lectures/lect12c.P
    
    
    
    % Reflecting on scrapSort:
    %   Consider the *order* of solutions when we try:
    %   permutation([3,4,5],X).
    %   permutation([5,4,3],X).
    % How *many* permutations does scrapSort([3,4,5],X) look at?
    % How about scrapSort([5,4,3],X) ?
    %
    % Now, consider this problem amplified:
    %     scrapSort([8,7,6,5,4,3,2,1],X).  runs okay. But
    % But scrapSort([10,9,8,7,6,5,4,3,2,1],X).  takes a moment (~2.5s).
    %     scrapSort([11,10,9,8,7,6,5,4,3,2,1],X).  takes too long (~27s).
    % 
    %
    % The name "scrapSort" was chosen because its performance
    % is a piece of scrap: O(n!).
    
    
    
    
    
    
    % Ironically, 'quicksort' is more straightforward than 'scrapsort',
    % even though we specify *how* to sort rather than *what sorted means*.
    %
    
    qsort([],[]).
    qsort([F|R],L2) :- partition([F|R],F,Sm,Eq,Bg), 
                       qsort(Sm,SmSorted), 
                       qsort(Bg,BgSorted), 
                       append3(SmSorted,Eq,BgSorted,L2).
    
    /* [+,+,-,-,-]
       partition(Lst,Pivot,Smalls,Equals,Larges) :
       partition Lst into those elements that are smaller, equal-to, and larger than Pivot.
       */
    partition([],_,[],[],[]).
    partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
      F<Pivot,
      Smallers = [F|SmallerRest],
      partition(R,Pivot,SmallerRest,Equals,Biggers).
    partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
      F=Pivot, 
      Equals = [F|EqualRest],
      partition(R,Pivot,Smaller,EqualRest,Biggers).
    partition([F|R],Pivot,Smallers,Equals,Biggers) :- 
      F>Pivot, 
      Biggers = [F|BiggerRest],
      partition(R,Pivot,Smallers,Equals,BiggerRest).
    
    /* N.B. You can remove the '=' terms from the above lines,
       reducing the code by 4 lines.  Left in for clarity (?).
      */
    
    % Note that we partition into *three* sections,
    % so that we always *reduce* the size of a partition
    % (even if our pivot is the maximum value).
    % Study the sol'n above, to see how the Prolog
    % makes sure we always recur on smaller lists (even
    % when the pivot is the maximum (or minimum) value.
    
    
    
    
    
    
    /* appendThree(L1,L2,L3,All) : All is the elements of L1 appended to L2 appended to L3. */
    appendThree(L1,L2,L3,All) :- append(L1,L2,L1and2), append(L1and2,L3,All).
    
    /* The following is the same as the append/3 included with [basics]. */
    append([],L2,L2).
    append([F|R],L2,[F|AllRest]) :- append(R,L2,AllRest).

(define (qsort1 nums)
  (cond [(empty? nums) empty]
        [else 
         (define pivot  (first nums))
         (define smalls (filter ((curry >) pivot) nums))
         (define equals (filter ((curry =) pivot) nums))
         (define bigs   (filter ((curry <) pivot) nums))
         (append (qsort1 smalls) equals (qsort1 bigs))]))

quicksort []     = []
quicksort (p:xs) = (quicksort smalls) ++ equals ++ (quicksort bigs)
    where
        smalls  = filter (< p) xs
        equals  = p : filter (= p) xs
        bigs    = filter (> p) xs

qsort [] = []
qsort (p:xs) = qsort [x | x<-xs, x<p]  ++  [x | x<-xs, x=p]  ++  qsort [x | x<-xs, x>=p]

public class Quicksort  {
  private double[] numbers;  // Make a field, so we don't have to pass it around each recursive call.

  public static void sort(double[] values) {
    if (!(values==null || values.length==0)) {
      new Quicksort( values ).quicksort(0, values.length-1);
      }
    }

  /* Modify this.numbers so that is sorted for indices in [low,high]. 
   */
  private void quicksort(int low, int high) {
    int i = low, j = high;
    double pivot = this.numbers[low];

    // Partition into two lists:
    // On the left, everything less than the pivot, and 
    // on the right, everything more than the pivot.
    // Wherever i,j meet is the partition.
    while (i <= j) {
      // Advance i to the first number that isn't less than the pivot.
      // (This is a number that *shouldn't* be on the left.)
      while (numbers[i] < pivot) { ++i; }
      // Likewise, decrease the right edge.
      while (numbers[j] > pivot) { --j; }

      // If we have found a value in the left list which is larger then
      // the pivot element, and we have found a value in the right list
      // which is smaller then the pivot element, then we exchange the values.
      // Then advance over those now-correctly-placed values, and continue.
      if (i <= j) {
        swapAt(i, j);
        i++;
        j--;
        }
      }
        
    // Now, recur, and we'll be done (since we're in-place, no need to append results):
    if (low < j)  quicksort(low, j);
    if (i < high) quicksort(i, high);
    }

  private void swapAt(int i, int j) {
    double temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
    }

  }
  

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}
/* From http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell */