leetwinski
2020-12-04 00:56:22
i guess you're overthinking it.
you have two tasks:
- insert item at the proper position inside a sorted collection
- return vector for input vector and list for input list
first of all, i would rewrite the insert-x like this for example:
(defn insert-x [sorted-coll x]
(let [[l r] (split-with #(<= % x) sorted-coll)]
`(~@l ~x ~@r)))
notice, it does more or less the same that your variant does: taking values until the desired positions, and then concatenating left and right parts with x between them. notice also, it always produces properly sorted list, independent from the input type.
user> (insert-x [1 3 5 7 9] 10)
;;=> (1 3 5 7 9 10)
user> (insert-x [1 3 5 7 9] 0)
;;=> (0 1 3 5 7 9)
user> (insert-x [1 3 5 7 9] 4)
;;=> (1 3 4 5 7 9)
so, the next thing you need, is just to reduce input and return the properly typed result:
(defn my-sort [coll]
(let [sorted (reduce insert-x () coll)]
(if (vector? coll)
(vec sorted)
sorted)))
user> (my-sort '(0 3 1 4 2 5 10 7))
;;=> (0 1 2 3 4 5 7 10)
user> (my-sort [0 3 1 4 2 5 10 7])
;;=> [0 1 2 3 4 5 7 10]
user> (my-sort ())
;;=> ()
user> (my-sort [])
;;=> []
热门帖子
热门github
6
This is likely to cause a stack overflow for moderately sized collections,
(my-sort (shuffle (range 1000))), due to stacking of lazyconcatand lazysplit-with.@A.Webb . Sure, but since it seems to be the education-only task (who would really use this in production?) that will do. Otherwise
(doall `(~@l ~x ~@r))solves this.@leetwinski how would you approach it in production? (built-in sort functions?)
@Gwang-JinKim it essentially depends on your task and input size. Generally, built-in
sortis good enough, so you should consider optimizing it iff it is necessary. You could also take a look at sorted-sets, in in case you need to keep your changing data sorted, which is better then resorting it every time it changes. But again, we can't reason about it unless we have any task specific information