4 ms·
If your sort is lazy enough, the `(sort xs) !! k` approach will work fine. Haskell's default sort isn't lazy enough, but you could certainly make it so. You do
by sgk284 13y ago
If your sort is lazy enough, the `(sort xs) !! k` approach will work fine. Haskell's default sort isn't lazy enough, but you could certainly make it so.
You don't have to fully sort the list before determining the kth element (again assuming a sufficiently lazy implementation). Once you know the element is in the second half of the list, the sort simply will never sort the first half.
- bdonlan 13y agoIt should be noted that the additional overhead from performing lazy quicksort (all those additional thunks) make it an unlikely choice for the standard sort function; you'd suffer a large constant factor overhead in the typical case of processing the entire list in sorted order.
- sgk284 13y agoYep, definitely should have noted that. It's an interesting mental exercise though.