Безкраен цикъл в бързото сортиране на SML?

И така, написах тази функция за бързо сортиране в SML, за да използвам сгъването на функцията от висок ред, но тя се задържа в безкраен цикъл и не мога да определя грешната логика, която го причинява. Някакви предложения къде да търся?

(* takes in a list of numbers and an arbitrary binary relation function f *)
fun quicksort nil f  = []
  | quicksort [x] f  = [x]
  | quicksort list f =
        let
            (* simply choose pivot as first item in the list *)
            val pivot = hd list
            (* lists iterated by folding for numbers pertaining to the relation f 
               or its converse *)
            fun test a  = List.foldr (fn (x,y) => if f (pivot, x) then x::y else y) [] a
            fun testC a = List.foldr (fn (x,y) => if f (pivot, x) then y else x::y) [] a
        in
            (* my notion is the function is looping here, since the functions test 
               and testC work fine on their own *)
            quicksort (test list) op f @ [pivot] @ quicksort (testC list) op f
        end;

Благодаря за всякакви предложения.


sml
person c0nn    schedule 07.02.2014    source източник


Отговори (1)


Проблемът е, че подсписъците, на които извиквате quicksort, могат да бъдат дълги като първоначалния списък. Трябва да се уверите, че обобщеният елемент не може да бъде в тези списъци.

Най-лесният начин да направите това е да използвате съвпадение, за да разделите входящия списък на pivot и списък с оставащи елементи и след това да предадете този списък на тестовите функции.

person gsg    schedule 07.02.2014