; Question 1
; This solution uses the Euclidean distance metric. The Manhattan (sum of the
; two side lengths) distance metric is also acceptable. The maximum length
; metric is also accceptable, although it is an unusual choice.
; Many students observed that it isn't necessary to take the square root when
; performing the Euclidean distance metric. This is acceptable because we are
; comparing distances and aren't interested in the actual values.
; First a few functions to make things a little more readable. Most of them are
; from part II of the homework.
(define (square x) (* x x))
(define (mp x y) (list x y))
(define x-point car)
(define y-point cadr)
(define (distance p)
(sqrt (+ (square (x-point p)) (square (y-point p)))))
; Now the closer-than? function.
(define (closer-than? p1 p2)
(if (and (= (length p1) 2) (= (length p2) 2))
(< (distance p1) (distance p2))
(error "error in input")
)
)
; Question 2
; The relative order of points in the original list should be maintained but
; it's not essential if we are using partition-points in the quicksort function.
(define (partition-points x lst)
(if (null? lst) (list '() '())
(let ((head (car lst))
(partitioned-rest (partition-points x (cdr lst))))
(if (closer-than? head x)
(list (cons head (car partitioned-rest)) (cadr partitioned-rest))
(list (car partitioned-rest) (cons head (cadr partitioned-rest)))
)
)
)
)
; Tail recursive version. Note that the helper function is defined within
; the main function, so 'x' can be referred to without passing it into the
; helper function itself.
; This version ends up with the order of the points in each of the lists
; returned being reversed, which doesn't actually matter for quicksort.
(define (cons-first-list x lst) (list (cons x (car lst)) (cadr lst)))
(define (cons-second-list x lst) (list (car lst) (cons x (cadr lst))))
(define (partition-points-tail-recursive x lst)
(define (partition-points-helper return-list lst)
(if (null? lst) return-list
(let ((head (car lst))
(tail (cdr lst)))
(if (closer-than? head x)
(partition-points-helper
(cons-first-list head return-list) tail)
(partition-points-helper
(cons-second-list head return-list) tail)
)
)
)
)
(partition-points-helper '(() ()) lst)
)
; Question 3
; The 'pivot' element is always the first element of the list. This gives
; abysmal performance if the list is sorted ascending or descending. However
; this question isn't about performance.
(define (quicksort-points lst)
(if (null? lst) '()
(let ((pivot (car lst)))
(let ((partitioned (partition-points pivot (cdr lst))))
(let ((sorted-bottom (quicksort-points (car partitioned)))
(sorted-top (quicksort-points (cadr partitioned))))
(append sorted-bottom (list pivot) sorted-top)
)
)
)
)
)