Consider the following function definition:
1. var qs = function (ns) { 2. if (fp.isNull(ns)) { 3. return [ ]; 4. } else { 5. return join( 6. fp.hd(split(fp.hd(ns),fp.tl(ns))), 7. fp.cons(fp.hd(ns), 8. fp.hd(fp.tl(split(fp.hd(ns),fp.tl(ns))))) 9. ); 10. } 11. };
The qs
function above takes as input a (flat) list of integers and
uses the split
and join functions to compute
its output.
Now, you want this function to sort any
list of integers in ascending order. Instead it behaves
in the following way:
> qs([5,1,9,2,7,3]) [ 3, 2, 1, 5, 7, 9 ]
Which one of the following options best characterizes the line(s) that will have to change to solve this problem?
Make sure to review how the split and join functions work.
Observe that the input list is split into two parts using its head as a pivot and then put back together in a different order.
What is special about the position of the pivot in this reordering of the input list?
Take the recursive leap of faith, and voilà!