I'm working on an extra assignment where the partition function of a quicksort in SML may only be done with foldr, and no library functions may be used. I've gotten the partitioning down just fine, and have the fundamentals of quicksort just fine, but am running into problems where it seems to merge the wrong lists together/merge in the wrong order.
(*comp is a placeholder, I will be given a comparator function and list as input*)
fun comp a b = a > b;
(*Both partition functions are working as intended.*)
fun getGreater (a::b) c = foldr (fn (a, lst) => if (comp a c) then a::lst else lst) [] (a::b);
fun getLesserOrEqual (a::b) c = foldr (fn (a, lst) => if not (comp a c) then a::lst else lst) [] (a::b);
fun merge (a::b) (c::d) = foldr (op::) (c::d) (a::b);
fun tripleMerge (a::b) c (d::e) = merge (a::b) (c::(d::e));
(*Removes head, uses head as pivot. Recursive calls on results on getLesserOrEqual and getGreater*)
fun sort [] = [] | sort (a::b) = if ([a] = (a::b)) then [a] else
tripleMerge (sort(getLesserOrEqual b a)) a (sort(getGreater b a));
As an example, here are some of the tests I'm running. When I follow my logic on paper, I don't get the same answers as the incorrect items:
sort [2, 6, 3, 6, 4, 100, 0];
val it = [0,2,3,6,4,6,100] : int list (*Incorrect*)
sort [1, 2, 3, 4, 5];
val it = [1,2,3,4,5] : int list
sort [5, 4, 3, 2, 1];
val it = [5,4,3,2,1] : int list (*incorrect*)
sort [1, 100, 10, 1000, 0];
val it = [0,1,10,100,1000] : int list
sort [1, 2, 1, 2, 1, 2, 5, 1];
val it = [1,1,1,1,2,2,2,5] : int list
Is my mistake obvious to anyone?
The only mistake I see is in your merge and tripleMerge functions. By using patterns like a::b you are disallowing empty lists. But -- when the pivot is either the smallest or the greatest element, than one of your partitioning functions will be returning empty lists. If you tweak the code of those two functions like this:
fun merge xs ys = folder (op::) ys xs;
fun tripleMerge xs y ys = merge xs (y::ys);
and leave the rest of the code alone, it will work as expected.