The following live code snippet (modified from the previous lab) randomly generates sorting problems problems for you to work through with your partner.
For the first two problems, trace through the step-by-step execution of the algorithm using insertion sort as demonstrated in the reading. You can choose to represent the input to insertion sort either as a list or a vector.
For the third problem, trace through the step-by-step execution of the merge algorithm on the two lists as demonstrated in the reading.
For the fourth problem, trace through the step-by-step execution of merge sort on the list as demonstrated in the reading.
Like before, the Gradescope turn-in is an online assignment that you can directly write your results into. Since this code is live, feel free to refresh this page for fresh problems to work on for practice!
;;; (for-each l f) -> void
;;; l: list?
;;; f: procedure?
;;; Runs (f v) for each v found in l in left-to-right order, discarding
;;; any return values generated by the calls.
(define for-each
(lambda (l f)
(match l
[null void]
[(cons head tail)
(begin
(f head)
(for-each tail f))])))
;;; (shuffle! vec) -> void
;;; v: vector?
;;; Mutates vec by shuffling its elements.
;;; (Note: the fisher-yates shuffle, implemented directly from Wikipedia:
;;; https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
(define shuffle!
(lambda (vec)
(let ([n (vector-length vec)])
(for-each (range 0 (- n 2))
(lambda (i)
(let* ([j (+ (random (- n i)) i)]
[tmp (vector-ref vec i)])
(begin
; swap vec[i] and vec[j]
(vector-set! vec i (vector-ref vec j))
(vector-set! vec j tmp))))))))
;;; (list-split l n) -> pair?
;;; l: list?
;;; n: integer?, a valid index into l
;;; Returns a pair of lists that is the result of splitting l
;;; at index n.
(define list-split
(lambda (l n)
(if (zero? n)
(pair null l)
(match l
[null (error "list-split: index out of bound")]
[(cons head tail)
(let ([result (list-split tail (- n 1))])
(pair (cons head (car result)) (cdr result)))]))))
;;; (list-split-half l) -> pair?
;;; l: list?
;;; Returns a pair of lists that is the result of splitting l in half.
(define list-split-half
(lambda (l)
(list-split l (floor (/ (length l) 2)))))
;;; (make-shuffled-vector n) -> vector?
;;; n: integer? non-negative
;;; Returns a newly allocated, shuffled vector with the values 0--(n-1).
(define make-shuffled-vector
(lambda (n)
(let* ([vec (vector-range n)])
(begin
(shuffle! vec)
vec))))
;;; (make-sorted-vector n k) -> vector?
;;; n, k: integer? non-negative
;;; Returns a newly allocated, sorted vector of size k. Each successive
;;; element is at most k+1 away from the previous one.
(define make-sorted-vector
(lambda (n k)
(let* ([vec (vector-range n)])
(begin
(for-each (range n)
(lambda (i)
(vector-set! vec i (+ (if (> i 0) (vector-ref vec (- i 1)) 0)
(random k)
1))))
vec))))
; Problem (a): insertion sort
(make-shuffled-vector 10)
; Problem (b): insertion sort, again!
(make-shuffled-vector 10)
; Problem (c): merge algorithm
(make-sorted-vector 5 10)
(make-sorted-vector 5 10)
; Problem (d) merge sort
(make-shuffled-vector 16)