;-------------------------------------------------------------
; Edgar Olijar & Robin Bertram
; Tutor: Jonas Blumenstein
; Übungsgruppe: Mittwoch 17-19 Uhr, C9G09
;-------------------------------------------------------------

; sorted? gibt an, ob eine liste von natürlichen Zahlen aufsteigend sortiert ist
; dabei dürfen auch gleiche Zahlen direkt hintereinander stehen.
(: sorted? ((list-of real) -> boolean))
(check-expect (sorted? (make-pair -5 (make-pair 5 (make-pair 120 empty)))) #t)
(check-expect (sorted? (make-pair 2 (make-pair 1 (make-pair 120 empty)))) #f)
(check-expect (sorted? (make-pair 1 (make-pair 1 (make-pair 120 empty)))) #t)
(define sorted?
  (lambda (lis)
    (cond ((or (empty? lis) (empty? (rest lis)))
           #t)
          ((pair? (rest lis))
           (if (> (first lis) (first (rest lis)))
               #f
               (sorted? (rest lis)))))))

;definiere eine Signatur für aufsteigend sortierte Listen von Zahlen
(define sorted (signature (predicate sorted?)))

; Die Prozedur insert-sorted konsumiert eine Zahl und eine sortierte Liste
; von Zahlen und fügt diese Zahl an der richtigen Stelle in die Liste ein
; (so dass die Liste wieder sortiert ist)
(: insert-sorted (real sorted -> sorted))
(check-expect (insert-sorted 23 (make-pair 3 (make-pair 12 (make-pair 45 (make-pair 113 empty)))))
              (make-pair 3 (make-pair 12 (make-pair 23 (make-pair 45 (make-pair 113 empty))))))
(check-within (insert-sorted 4.3 empty) (make-pair 4.3 empty) 0.001)
(check-within (insert-sorted -2.78 (make-pair -2.78 empty))
              (make-pair -2.78 (make-pair -2.78 empty)) 0.0000001)
(define insert-sorted
  (lambda (x lis)
    (cond ((empty? lis) (make-pair x empty))
          ((pair? lis)
           (if (> x (first lis))
               (make-pair (first lis) (insert-sorted x (rest lis) ) )
               (make-pair x lis))))))

; Prozedur sort-list sortiert Zahlen in einer Liste lis
(: sort-list ((list-of real) -> sorted))
(check-within (sort-list (make-pair 5 (make-pair 99 (make-pair -5 empty))))
              (make-pair -5 (make-pair 5 (make-pair 99 empty))) 0.0001)
(check-expect (sort-list (make-pair 4 empty))
              (make-pair 4 empty))
(check-expect (sort-list empty) empty)
(define sort-list
  (lambda (lis)
    (if (sorted? lis)
        lis
        (insert-sorted (first lis) (sort-list (rest lis))))))