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

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

; test cases for min
(check-expect (min '(1 2 3)) 1)
(check-expect (min '(2 1 3)) 1)
(check-expect (min '(2 3 1)) 1)
(check-expect (min '(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   (min 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))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;          Bubble Sort            ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; bubble does one pass of flipping the order of sequential
;    pairs that are out of order
(define (bubble L)
  (if (or (null? L) (null? (rest L)))
      L
      (let ([element1 (first L)]
            [element2 (second L)])
        (if (> element1 element2)
            (cons element2 (bubble (cons element1 (rest (rest L)))))
            (cons element1 (bubble (cons element2 (rest (rest L)))))))))

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

; bubbleSort uses the bubble sort algorithm to sort the unsorted 
;     list L. 
(define (bubbleSort L)
; todo write bubbleSort
  )

; test cases for bubble sort
(check-expect (bubbleSort '()) '())
(check-expect (bubbleSort '(1)) '(1))
(check-expect (bubbleSort '(3 2 1)) '(1 2 3))
(check-expect (bubbleSort '(1 4 2 3)) '(1 2 3 4))
(check-expect (bubbleSort '(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))

(generate-report)