sort.zp

(define (sort:sorted? seq . ord)
  "checks whether sequence is sorted. Optionally takes an order function,
   the default is <fun>lt</fun>.

   params:
     - seq: the sequence to sort
     - ord: the order function (default: <fun>lt</fun>)
   complexity: O(n)
   returns: boolean"
  (let ((ord (if (null? ord) lt (list:ref ord 0))))
  (if (< (length seq) 2)
    #t
    (and (ord (car seq) (cadr seq)) (sort:sorted? (cdr seq) ord)))))

(define (sort:_split l)
  (define (_split l ls1 ls2)
                      (if (< (length l) 2)
                        (cons (reverse ls2) ls1))
                        (_split (cddr l) (cdr ls1) (cons (car ls1) ls2)))
    (_split l l '()))

(define (sort:merge a b . ord)
  "Merge two sorted sequences. Optionally takes an order function,
   the default is <fun>lt</fun>.

   params:
     - a: the first sequence
     - b: the second sequence
     - ord: the order function (default <fun>lt</fun>)
   complexity: O(n)
   returns: the merged sequence"
  (let ((ord (if (null? ord) lt (list:ref ord 0))))
  (cond
    ((null? a) b)
    ((null? b) a)
    (else (let loop
               ((x (head a))
                (a (tail a))
                (y (head b))
                (b (tail b)))
        (if (ord y x)
          (if (null? b)
            (cons y (cons x a))
            (cons y (loop x a (car b) (cdr b))))
          (if (null? a)
            (cons x (cons y b))
            (cons x (loop (car a) (cdr a) y b)))))))))

(define (sort:quicksort l . ord)
  "sort a list with quicksort scheme. Optionally takes an order function,
   the default is <fun>lt</fun>.

   params:
     - l: the list to sort
     - ord: the order function (default is <fun>lt</fun>)
   complexity: O(n*log(n))
   returns: the sorted list"
  (let ((ord (if (null? ord) lt (list:ref ord 0)))
        (i (randint 0 (length l))))
  (if (< (length l) 2)
    l
    (let loop ((left []) (right []) (h (get-from l i)) (t (list:remove-n l i)))
      (if (null? t)
        (++ (++ (sort:quicksort left ord) (list h)) (sort:quicksort right ord))
        (if (ord (car t) h)
          (loop (++ left (list (car t))) right h (cdr t))
          (loop left (++ right (list (car t))) h (cdr t))))))))

(define (sort:mergesort l . ord)
  "sort a list with mergesort scheme. Optionally takes an order function,
   the default is <fun>lt</fun>.

   params:
     - l: the list to sort
     - ord: the order function (default: <fun>lt</fun>)
   complexity: O(n*log(n))
   returns: the sorted list"
  (let ((ord (if (null? ord) lt (list:ref ord 0))))
  (if (< (length l) 2)
    l
    (let ((splits (sort:_split l)))
      (sort:merge
        (sort:mergesort (car splits) ord)
        (sort:mergesort (cdr splits) ord) ord)))))

(define (sort:_insert x lst . ord)
  (let ((ord (if (null? ord) lt (list:ref ord 0))))
    (if (null? lst)
        (list x)
        (let ((y (car lst))
              (ys (cdr lst)))
          (if (ord x y)
              (cons x lst)
              (cons y (insert x ys)))))))

(define (sort:insertionsort lst . ord)
  "sort a list with insertionsort scheme. Optionally takes an order function,
   the default is <fun>lt</fun>. It is really slow.

   params:
     - l: the list to sort
     - ord: the order function (default: <fun>lt</fun>)
   complexity: O(n^2)
   returns: the sorted list"
  (let ((ord (if (null? ord) lt (list:ref ord 0))))
    (if (null? lst)
        '()
        (sort:_insert (car lst) (sort:insertionsort (cdr lst)) ord))))

(define sort:sort sort:quicksort)