Sort of stumped on how to approach this one. I have to write a function that will sort a list according to a predicate but we’re not allowed to use any of Clojure’s built-in sorting functions or consult their source code for our solution. Wondering if anyone has any suggestions. Same runs are below:
I can use take, drop and a merge-pred function we’ve been provided with (see here). The arguments for merge-pred have to already be sorted according to the predicate when they’re entered as arguments. I’ve been told look to the Merge Sort algorithm and I understand how it works, but I don’t know how to write something that mimics that in Clojure, using take and drop.
Merge-Pred makes sense because I would use the predicate of sort-pred and my two lists would be the list argeument of sort pred split in half, but already sorted. It’s the already sorted part I’m stuck on.
Your existing merge-pred function could accept two one-element lists and produce a two-element list that is sorted. Then it could accept that two-element sorted list and another one-element list and produce a three-element list that is sorted. A one-element list is always sorted (by definition since it includes only one element).
Yeah. I guess I’m just not understanding how to get there. I know merge-pred can merge any size of two lists together. I’m just not sure how to get there or even sort the list before calling that function.
and I want to build a new list that is sorted, as @seancorfield points out, we already have a way to construct a sorted list from two “sorted” lists in merge-pred.
So if we revisit our definition of a sorted list, then '(4) is sorted, '() is sorted, etc. If we have two lists, '() and '(4), and we pass them to merge-pred:
user> (merge-pred <= '() '(4))
;;(4)
we get a sorted list back. Since the inputs are “guaranteed” to be sorted, it seems like we can leverage this property again…
Extending that approach, we could dice it up this way too:
user> (def l (merge-pred <= '(4) '(3)))
#'user/l
user> (def r (merge-pred <= '(2) '(1)))
#'user/r
user> l
(3 4)
user> r
(1 2)
user> (merge-pred <= l r)
(1 2 3 4)
Maybe there exists a higher order function that can leverage merge-pred to do what we did in the repl automatically.; if we can derive such a function, it appears to produce a useful result.
Also an approach I often find useful is to ask the question: if we were already able to solve same problem of smaller size, would it be useful in our implementation?
I.e. when trying to come up with implementation for (sort-pred p xs), I’d try and ask: if sort-pred already worked correctly for all inputs smaller than xs, could I use it to my advantage?
Just as inside your implementation of merge-pred you use merge-pred itself on smaller inputs, this might be helpful to come up with an implementation of sort-pred.