Hey all,
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:
> (sort-pred <= ’(8 9 5 -1 0 2 3 -15))
(-15 -1 0 2 3 5 8 9)
> (sort-pred >= ’(8 9 5 -1 0 2 3 -15))
(9 8 5 3 2 0 -1 -15)
what do you know about sorting?
What functions / forms from the clojure core library are you restricted to?
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).
Does that help?
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.
If I have the list
(def xs '(4 3 2 1))
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…
user> (merge-pred <= '(4) '(3))
(3 4)
user> (merge-pred <= '(3 4) '(2))
(2 3 4)
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.