#lang racket
(require htdp/testing)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;          Selection Sort         ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; minL returns the smallest element in the list
(define (minL L) 
  ; todo write min
  )

; test cases for min
(check-expect (minL '(1 2 3)) 1)
(check-expect (minL '(2 1 3)) 1)
(check-expect (minL '(2 3 1)) 1)
(check-expect (minL '(1 1 1)) 1)

; remove removes the first instance of the element x from the list
; We assume that remove will only be called if there 
;    is at least one instance of x in the list L.
(define (remove x L)
  ; todo write remove
  )

; test cases for remove
(check-expect (remove 1 '(1 2 3)) '(2 3))
(check-expect (remove 1 '(2 1 3)) '(2 3))
(check-expect (remove 1 '(2 3 1)) '(2 3))
(check-expect (remove 1 '(1 1 1)) '(1 1))
(check-expect (remove 1 '(1))     '())

; selectionSort sorts an unsorted list L using selection sort
(define (selectionSort L)
  (if (null? L) 
      L
      (let* ([minimum   (minL L)]
             [remaining (remove minimum L)])
        (cons minimum (selectionSort remaining)))))
  
; test caess for selectionSort
(check-expect (selectionSort '()) '())
(check-expect (selectionSort '(1)) '(1))
(check-expect (selectionSort '(3 2 1)) '(1 2 3))
(check-expect (selectionSort '(1 4 2 3)) '(1 2 3 4))
(check-expect (selectionSort '(10 6 15 4 1 11 7 1 14 9 9 2 5 3 13 8)) 
              '(1 1 2 3 4 5 6 7 8 9 9 10 11 13 14 15))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;          Insertion Sort         ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; insert the element x into the sorted list L
(define (insert x L)
; todo write insert
  )

; test cases for insert
(check-expect (insert 1 '(3)) '(1 3))
(check-expect (insert 3 '(1)) '(1 3))
(check-expect (insert 3 '(1 2 4)) '(1 2 3 4))
(check-expect (insert 1 '()) '(1))

; insertionSort uses the insertion sort algorithm to sort 
;    the unsorted list Unsorted
(define (insertionSort Unsorted)
  (insertionSortH Unsorted '()))

; the helper method insertionSort keeps track of a sorted 
;    and unsorted portion of the list to successively insert
;    an element from Unsorted into the list Sorted.
(define (insertionSortH Unsorted Sorted)
  (if (null? Unsorted) 
      Sorted
      (insertionSortH (rest Unsorted) (insert (first Unsorted) Sorted))))

; test cases for insertionSort
(check-expect (insertionSort '()) '())
(check-expect (insertionSort '(1)) '(1))
(check-expect (insertionSort '(3 2 1)) '(1 2 3))
(check-expect (insertionSort '(1 4 2 3)) '(1 2 3 4))
(check-expect (insertionSort '(10 6 15 4 1 11 7 1 14 9 9 2 5 3 13 8)) 
              '(1 1 2 3 4 5 6 7 8 9 9 10 11 13 14 15))