CODEWITHSUNDEEP
ocaml
Peter Hwang
Peter Hwang

Reputation: 991

Ocaml Insertion Sort

Input: Unsorted list / Output: Sorted list

My basic idea is insert an integer into the sorted list.

(I can sort the list if I could insert the first element into the sorted tails.)

I used "insert", which is thehelper function.

However, it gets overflow. Couuld anyone tell me what the problem is?

let rec sort (l: int list) : int list =
    match l with
        []->[]
      | x::[]->[x]
      | x1::x2::xs->let rec insert (n,dest) =
                            match dest with
                                []->[n]
                              | y::[]-> if n<y then [n;y] else [y;n]
                              | y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)
                    in insert(x1,sort(x2::xs)) ;;

Upvotes: 2

Views: 4218

Answers (3)

Oleg
Oleg

Reputation: 1559

Always when asking such questions , it's hard for people to read such code and mostly they will ignore the post. Like @Thomash said, first of all try to divide into smaller functions, this way it's easier to see where it fails.

you can "debug with your eye" this:

let rec insertion_sort el = function  
    | [] -> [el]
    | h::t as ls -> if el > h then h :: insert el t else (el :: ls) 

let sorted_list ls = List.fold_right insertion_sort ls []

Upvotes: 2

Thomash
Thomash

Reputation: 6379

Again, I have style suggestions:

  • You should separate the two functions sort and insert because it would make it more readable and also because the insert function can be useful in itself.
  • Why do you give a tuple as argument to the insert function? In OCaml, one would use currying and write insert x l instead of insert(x,l). This would allow you to do partial application.
  • Why do you restrict the type of your function to int list -> int list. Functions in OCaml can be polymorphic, so your function should have the more generic type 'a ist -> 'a list.

Here is the code you obtain with all these corrections:

let rec insert x l =
  match l with
    | [] -> [x]
    | y::ys -> if x < y then x::y::ys else y::insert x ys

let rec sort l =
  match l with
    | [] -> []
    | x::xs -> insert x (sort xs)

Upvotes: 7

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66813

This line looks pretty wrong to me:

| y1::y2::ys-> if y1<y2 then n::dest else y2::insert(y1,xs)

It seems to me that you know your ys are sorted (by induction hypothesis). So you should be comparing n against your ys, not your ys against each other. If you get this line straightened out things will probably improve.

For what it's worth, I suspect you only need to have two cases in your match. I don't see why you need to treat a 1-element list differently from any other non-null list.

Upvotes: 4

Related Questions