;;; ======================================
;;;  CMPU-181, Spring 2013
;;;  Feb. 11, 2013
;;;  Comparison of Sorting Algorithms
;;; ======================================
;;;  Defines an implementation of the BUBBLE-SORT algorithm,
;;;  two implementations of the MERGE-SORT algorithm.  Also
;;;  defines a testing function to enable comparisons among
;;;  these sorting algorithms and the built-in SORT function.

;;;  ====> For asmt3, use the SORTING-TEST function.
;;; ---------------------------------------------------------
;;;   Here are some examples of its use:
;;;      (sorting-test 1000 (list merge-sort bubble-sort))
;;;      (sorting-test 2000 (list merge-sort built-in-sort))


;;; ==============================
;;;  BUBBLE-SORT Algorithm
;;; ==============================

;;;  BUBBLE-ONE-PASS
;;; ----------------------------------
;;;  INPUTS:  LISTY, a list of numbers
;;;           NUM-LEFT, the number of comparisons left for this pass
;;;  OUTPUT:  The list that results from performing one pass of the 
;;;   bubble-sort algorithm (at most NUM-LEFT comparisons).

(define bubble-one-pass
  (lambda (listy num-left)
    (cond
      ;; Base Case:  We're finished this pass 
      ((or (<= num-left 0)
           (null? listy)
           (null? (rest listy)))
       ;; return LISTY
       listy)
      ;; Recursive Case 1:  First two items are in proper order
      ((<= (first listy) (second listy))
       ;; Keep FIRST item in place...
       (cons (first listy)
             ;; ... and continuing processing rest of list
             (bubble-one-pass (rest listy) (- num-left 1))))
      ;; Recursive Case 2:  First two items need to be swapped
      (#t
       ;; SECOND item now comes first...
       (cons (second listy)
             ;; ... and continue processing leftover portion of list
             (bubble-one-pass (cons (first listy) (rest (rest listy)))
                              (- num-left 1)))))))

;;;  BUBBLE-MULTI-PASS
;;; --------------------------------------
;;;  INPUTS:  LISTY, a list of numbers
;;;           NUM, the number of passes to perform
;;;  OUTPUT:  The list that results from performing NUM passes of the 
;;;            BUBBLE-SORT algorithm on LISTY.

(define bubble-multi-pass
  (lambda (listy num)
    (cond
      ;; Base Case:  No more passes to do...
      ((<= num 0)
       ;; Return LISTY because we're done!
       listy)
      ;; Recursive Case:  Let BUBBLE-ONE-PASS run once,
      ;;  then use BUBBLE-MULTI-PASS on the result
      (#t
       (bubble-multi-pass (bubble-one-pass listy num)
                          (- num 1))))))

;;;  BUBBLE-SORT
;;; ---------------------------
;;;  INPUT:  LISTY, a list of numbers
;;;  OUTPUT:  A list containing the numbers from LISTY, but sorted
;;;            into non-decreasing order.  Uses the BUBBLE-SORT algorithm.

(define bubble-sort
  (lambda (listy)
    ;; Just call BUBBLE-MULTI-PASS with appropriate inpust
    (bubble-multi-pass listy (- (length listy) 1))))


;;; ============================================
;;;  The MERGE-SORT algorithm 
;;; ============================================


;;;  SPLITTY-ACC
;;; ------------------------------------------
;;;  INPUTS:  LISTY, a list 
;;;           LEFTY and RIGHTY, two accumulators
;;;  OUTPUT:  A list containing LEFTY and RIGHTY after the elements
;;;   of LISTY have been split among them (as evenly as possible).
;;;  -----------------------------------------
;;;  NOTE:  This function is an accumulator-based helper function
;;;         for SPLITTY (defined later).

(define splitty-acc
  (lambda (listy lefty righty)
    (cond
      ;; Base Case 1:  LISTY is empty
      ((null? listy)
       ;; So return the accumulators
       (list lefty righty))
      ;; Base Case 2:  Only one item left in LISTY
      ((null? (rest listy))
       ;; Return the accumulators... note that LEFTY gets the leftover item
       (list (cons (first listy) lefty)
             righty))
      ;; Recursive Case:  LISTY has at least 2 elements
      (#t
       ;; Tail-recursive function call... note that each accumulator
       ;; accumulates one of the items of listy.
       (splitty-acc (rest (rest listy))
                    (cons (first listy) lefty)
                    (cons (second listy) righty))))))

;;;  SPLITTY
;;; -----------------------------------------
;;;  INPUT:  LISTY, a list
;;;  OUTPUT:  A list containing two lists, each containing roughly
;;;   half the elements of LISTY.

(define splitty
  (lambda (listy)
    ;; Just call SPLITTY-ACC with accumulators initially empty
    (splitty-acc listy () ())))

;;;  MERGER-ACC
;;; ------------------------------------------------
;;;  INPUTS:  SORTY, SORTZ, two lists of numbers
;;;           ACC, an accumulator
;;;           INEQ-FUNC, an inequality function (e.g., either <= or >=)
;;;  OUTPUT:  A list containing all of the elements of SORTY and SORTZ
;;;    sorted according to the inequality function.  NOTE:  This function
;;;    is only guaranteed to work if SORTY and SORTZ are sorted.

(define merger-acc
  (lambda (sorty sortz acc ineq-func)
    (cond
      ;; Base Case:  Both SORTY and SORTZ are empty
      ((and (null? sorty) (null? sortz))
       ;; Return the accumulator
       acc)
      ;; Rec. Case 1:  First element of SORTY is going to go onto the accumulator
      ((and (not (null? sorty))
            (or (null? sortz)
                (ineq-func (first sorty) (first sortz))))
       (merger-acc (rest sorty) 
                   sortz 
                   (cons (first sorty) acc) 
                   ineq-func))
      ;; Rec. Case 2:  First element of SORTZ is going to go onto the accumulaor
      (#t
       (merger-acc sorty 
                   (rest sortz) 
                   (cons (first sortz) acc) 
                   ineq-func)))))

;;;  MERGER
;;; ---------------------------------
;;;  INPUTS:  SORTY, SORTZ, two sorted lists of numbers (according to INEQ-FUNC)
;;;           INEQ-FUNC, an inequality function (e.g., <= or >=)
;;;  OUTPUT:  A list containing all the elements of SORTY and SORTZ, sorted
;;;    into order determined by INEQ-FUNC.

(define merger
  (lambda (sorty sortz ineq-func)
    ;; Just call accumulator-based helper function with an empty accumulator
    (reverse (merger-acc sorty sortz () ineq-func))))

;;;  MERGE-SORT
;;; ------------------------------------------
;;;  INPUT:  LISTY, a list of numbers
;;;  OUTPUT:  A list containing the same elements as LISTY, except sorted
;;;    into non-decreasing order.  SORTED using the MERGE-SORT algorithm.

(define merge-sort
  (lambda (listy)
    (cond
      ;; Base Case:  LISTY is empty or contains only one element
      ((or (null? listy) (null? (rest listy)))
       ;; Thus, it is already sorted!
       listy)
      ;; Rec. Case:  LISTY has at least two elements
      (#t
       (let (;; Split LISTY into two sublists, each containing roughly half
             ;; the elements from LISTY
             (splitzies (splitty listy)))
         ;; SORT each sub-list (using MERGE-SORT), then MERGE the results
         (merger (merge-sort (first splitzies))
                 (merge-sort (second splitzies))
                 <=))))))

;;; ----------------------------------------------------------
;;;  Alternative Implementation of MERGE-SORT algorithm
;;; ----------------------------------------------------------

;;;  ALT-MERGE-SORT
;;; --------------------------------------------
;;;  An alternative version of MERGE-SORT that doesn't require SPLITTING.
;;;  Example.  If given a list like (1 4 3 2 9); first create the 
;;;  following list of lists: ((1) (4) (3) (2) (9)).  Then repeatedly
;;;  merge adjacent lists until there's only one (sorted) list remaining.

(define alt-merge-sort
  (lambda (listy)
    ;; Merge adjacent lists repeatedly until only one list remains
    (merge-pairs-until (map list listy))))

;;;  MERGE-PAIRS-UNTIL
;;; ---------------------------------------
;;;  INPUT:  LOL, a list of (already sorted) lists of numbers
;;;  OUTPUT:  A single list containing all the numbers in all the
;;;   sub-lists of LOL, sorted into non-decreasing order

(define merge-pairs-until
  (lambda (lol)
    (cond
      ;; Base Case:  LOL contains only one sub-list
      ((null? (rest lol))
       ;; We're done!  Return that sub-list.
       (first lol))
      ;; Recursive Case:  LOL contains at least 2 sub-lists
      (#t
       ;; Use MERGE-PAIRS-ACC to merge adjacent pairs of sub-lists in LOL
       ;; Then recursively call MERGE-PAIRS-UNTIL on the result
       (merge-pairs-until (merge-pairs-acc lol () <=))))))

;;;  MERGE-PAIRS-ACC
;;; ---------------------------------------------
;;;  INPUTS:  LOL, as above
;;;           ACC, an accumulator of merged sublists
;;;           INEQ-FUNC, an inequality function (eg., <= or >=)
;;;  OUTPUT:  A list of lists obtained by merging adjacent sub-lists
;;;           in LOL, together with the sub-lists already in the accumulator.

(define merge-pairs-acc
  (lambda (lol acc ineq-func)
    (cond
      ;; Base Case 1:  LOL is empty
      ((null? lol)
       ;; Return the accumulator
       acc)
      ;; Base Case 2:  LOL has only one sub-list
      ((null? (rest lol))
       ;; Return the accumulator plus that one sub-list
       (cons (first lol) acc))
      ;; 
      (#t
       ;; Recursive Case:  Use MERGER to merge the first two sub-lists in LOL
       ;;  Then call MERGE-PAIRS-ACC on the remaining sub-lists in LOL
       (merge-pairs-acc (rest (rest lol))
                        (cons (merger (first lol) (second lol) ineq-func)
                              acc)
                        ineq-func)))))


;;; =====================================
;;;  The "built-in" SORTING function
;;; =====================================

;;;  BUILT-IN-SORT
;;; ----------------------------------------
;;;  INPUT:  LISTY, a list of numbers
;;;  OUTPUT:  A list containing all the numbers from LISTY, but sorted
;;;    into non-decreasing order.  Uses the built-in SORT function.

(define built-in-sort
  (lambda (listy)
    (sort listy <)))


;;; ==========================================================
;;;  Functions for testing the above sorting functions
;;; ==========================================================

;;;  RANDOM-LIST
;;; ---------------------------
;;;  INPUTS:  LEN, number of elements in output list
;;;           UPPER-BOUND, upper-bound on numbers in output list
;;;  OUTPUT:  A list of length, LEN, each of whose elements is a number
;;;           from 0 to UPPER-BOUND - 1

(define random-list
  (lambda (len upper-bound)
    (cond
      ;; Base Case:  LEN = 0
      ((<= len 0)
       ;; Return a list containing 0 elements
       ())
      ;; Recursive Case: LEN > 0
      (#t
       ;; Use the built-in RANDOM function to generate the first
       ;; element of the output list, then use a recursive call
       ;; to RANDOM-LIST to generate the rest of the elements.
       (cons (random upper-bound)
             (random-list (- len 1) upper-bound))))))


;;;  SORTING-TEST
;;; -----------------------
;;;  INPUTS:  LEN, length of list to be sorted
;;;           SORTING-FUNCS, list of sorting functions to be tested
;;;  OUTPUT:  None
;;;  SIDE EFFECT: Prints out the time required to sort a randomly generated
;;;    list of length LEN using the indicated SORTING-FUNCS.
;;;    NOTE:  Although the list to be sorted is randomly generated, each
;;;           algorithm is applied to the same list.
;;; -----------------------
;;;  Sample use:  (sorting-test 1000 (list merge-sort bubble-sort))

(define sorting-test
  (lambda (len sorting-funcs)
    (let (;; LISTY is generated only once!
          ;; That way each sorting algorithm is applied to the same list
          (listy (random-list len (min len (* len len)))))
      ;; The following MAP expression applies each sorting function
      ;; to LISTY, printing out some timing statistics.
      (map (lambda (func)
             (printf "SORTING FUNC: ~A~%" func)
             (time (func listy))
             (newline))
           sorting-funcs))
    ;; Return () just for fun
    ()))