Tail Recursion: Difficult Solutions
code writing
Write in a tail recursive function that takes in a list and sorts it quickly. You may use the append function, which takes in two lists and puts them together. Hint: Write some helper functions to help you break down lst into three lists: values less than the car of lst, values equal to the car, and values greater than the car.
> (define lst '(3 7 2 6 7 8 7))
> (quicksort-tail-recursive lst)
(2 3 6 7 7 7 8)
(define (quicksort-tail-recursive lst)
(define (helper lst greater equal less)
(if (null? lst)
nil
(append (quicksort-tail-recursive (remove-less (cdr lst) (car lst) nil))
(append (remove-equal (cdr lst) (car lst) (list (car lst))) (quicksort-tail-recursive (remove-greater (cdr lst) (car lst) nil))))))
(define (remove-less lst x less)
(cond ((null? lst) less)
((< x (car lst)) (remove-less (cdr lst) x (cons (car lst) less))
(else (remove-less (cdr lst) x less))))
(define (remove-greater lst x greater)
(cond ((null? lst) greater)
((> x (car lst)) (remove-greater (cdr lst) x (cons (car lst) greater))
(else (remove-greater (cdr lst) x greater))))
(define (remove-equal lst x equal)
(cond ((null? lst) equal)
((> x (car lst)) (remove-equal (cdr lst) x (cons (car lst) equal))
(else (remove-equal (cdr lst) x equal))))