Q1

#lang racket
(require racket/contract)
(require rackunit)
(require rackunit/text-ui)

; Predicate to determine if the input is a list of integers.
; Input:   L is an arbitrary Racket object.
; Output:  boolean which is true if L is a list of integers and
;          false otherwise.
; Note:  The library function list? is a predicate to detect lists.
;        A predicate to detect lists of a given type can be obtained
;        from (flat-contract-predicate integer?)
(define (intlist? L)
  (if (null? L)
      #t
      (and (pair? L) (integer? (first L)) (intlist? (rest L)))))

; A predicate to determine if a list of integers is sorted.
; Input:  L a list of integers
; Output: boolean true of L is sorted false otherwise
(define (sorted? L)
   (cond
   [(null? L) #t]
   [(equal? (length L) 1) #t]
   [else (and (<= (first L) (second L))
         (sorted? (rest L)))]
   ))


; A predicate to determine if one list is permutation of another
; Input:  P and L are lists of integers
; Output: boolean which is true if L is a permutation of P
;         false otherwise.
(define (permutation? P L)
  (if (null? P)
      (null? L)
      (and (member (car P) L)
           (permutation? (remove (first P) P) (remove (first P) L)))))

; A function to insert an integer into a sorted list
; Input:  (and (integer? x) (intlist? L) (sorted? L))
; Output: (let (M (insert x L))
;              (and (intlist? M) (sorted? M) (permutation? M (cons x L))))
(define (insert x L)
  (cond
   [(null? L) (list x)]
   [(<= x (first L)) (cons x L)]
   [else (cons (first L) (insert x (rest L)))]
   ))

; A function to sort a list of integers using insertion sort
; Input:  (intlist? L)
; Output: (let (M (insertionsort L))
;              (and (intlist? M) (sorted? M) (permutation? M L)))
(define (sort3 L)
  (if (null? L)
    null
    (insert (first L) (sort3 (cdr L)))))

; Unit tests - tests all possible lists of three elements.



; insert definition of sort3 here.  Make sure you have comments that
; informally provide the input and output specifications for sort3.

(define-test-suite sort3-suite
  (check-equal?
    (sort3 '(1 2 3)) '(1 2 3))

  (check-equal?
    (sort3 '(1 3 2)) '(1 2 3))

  (check-equal?
    (sort3 '(2 1 3)) '(1 2 3))

  (check-equal?
    (sort3 '(2 3 1)) '(1 2 3))

  (check-equal?
    (sort3 '(3 1 2)) '(1 2 3))

  (check-equal?
    (sort3 '(3 2 1)) '(1 2 3))

  (check-equal?
    (sort3 '(1 1 2)) '(1 1 2))

  (check-equal?
    (sort3 '(1 2 1)) '(1 1 2))

  (check-equal?
    (sort3 '(2 1 1)) '(1 1 2))

  (check-equal?
    (sort3 '(1 1 1)) '(1 1 1))
)
(run-tests sort3-suite 'verbose)




; Unit tests - tests all possible lists of three elements.
; Copy the definition of the test suite insertionsort3-suite from
; above and rename it sort3-suite.  Make sure you replace calls to
; insertionsort by calls to sort3.  Then run sort3-suite using
; (run-tests insertionsort3-suite 'verbose)
; Make sure all tests pass.  If not you will need to debug your
; implementation of sort3.