CODEWITHSUNDEEP
ocamlquicksorttail-recursion
Juliana Souza
Juliana Souza

Reputation: 69

OCaml: Quicksort - Tail Recursion, infinite loop?

When I compile my code is ok, but when I call and execute the function Quicksort, the program seems to be in infinite loop. What Can I do ? I tested all the functions, but it seems the problem is in tQuicksort function. I'm a beginner.

let h l =
    match l with
        | [] -> raise (Failure "head")
        | x::xs -> x;;

let t l =
    match l with
        | [] -> raise (Failure "tail")
        | x::xs -> xs;;

let rec trev l r = 
    match l with
        | [] -> r
        | x::xs -> trev xs (x::r);;
let rev l = trev l [];;

let rec tunir l1 l2 r =
    match l1 with
        | [] -> if l2 == [] then
                rev r
            else
                tunir [] (t l2) ((h l2)::r)
        | x1::xs1 -> tunir xs1 l2 (x1::r);;


let unir l1 l2 = tunir l1 l2 [];;

let rec tpart x l l1 l2 = 
    match l with
        | [] -> if l1 == [] then
                ((x::[]), l2)
            else
                (l1, (x::l2))
        | (lx:: lxs) -> if (h l) <= x then
                    tpart x (t l) ((h l)::l1) l2
                else
                    tpart x (t l) l1 ((h l)::l2);;

let part x l = tpart x l [] [];;

let rec tnroelem l n =
    match l with
        | [] -> n
        | x::xs -> tnroelem (t l) (n+1);;

let nroelem l = tnroelem l 0;;

let rec tunirL l r = 
    match l with
        | [] -> rev r
        | lx::lxs -> if lx == [] then tunirL lxs r
                    else tunirL((t lx)::lxs) ((h lx)::r);;

let unirL l = tunirL l [];;

let rec tquicksort lm l lM = 
    match l with
        | [] -> unirL (unir (rev lm) lM)
        | lx::lxs -> let (la, lb) = part (h l) (t l) in
                    if (nroelem la < nroelem lb) then tquicksort ((quicksort la)::lm) lb lM
                    else tquicksort lm la ((quicksort lb)::lM)
and quicksort l = tquicksort [] l [];;

let rec geraListaT n l = 
    if n == 0 then l
    else geraListaT (n-1) (n::l);;
let geraLista n = geraListaT n [];;

let lista : int list = geraLista 9;;

List.iter (fun x->print_int x) (quicksort lista)

Upvotes: 2

Views: 288

Answers (1)

gallais
gallais

Reputation: 12103

You are missing a case when you're attempting to quicksort lm l lM and l only has one element. In that case the branch taken is

    | lx::lxs -> let (la, lb) = part (h l) (t l) in
                    if (nroelem la < nroelem lb)
                    then tquicksort ((quicksort la)::lm) lb lM
                    else tquicksort lm la ((quicksort lb)::lM)

And then no matter what the result of the if is, you perform a recursive call quicksort lm' l' lM' where l' also has only one element. This can be fixed by adding an extra case after the one for the empty list:

    | lx::[]  -> unirL (unir (rev (l :: lm)) lM)

Upvotes: 4

Related Questions