Noel Welsh wrote:
I think this is great code -- very clear. For production use you have the wrong data structure (Lists are O(n) random access and length; you want O(1) vectors), but that doesn't matter for your use.
I don't think vectors help very much in this case (median-finding). For the given code, the O(n) access to the middle of the list is dominated by the cost of the sorting, which is at least O(n log n) [*].
It is theoretically possible to compute the median in O(n) time, but the method is complicated and not very practical. But sorting definitely does too much work. If only the median (or the kth largest, a problem called "selection") is needed, a method which is both practical and of pedagogical interest stems from adapting Quicksort, which is a good exercise after section 25.2 of HtDP. This has expected cost O(n) on random data, and vectors offer no asymptotic advantage over lists. --PR
[*] Technically, "at least Omega(n log n)". _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
