Ocaml вставка Сортировка

Question

Вход: Unsorted список/вывод: упорядоченный список

Моя основная идея заключается в том вставить целое число в отсортированный список.

(я могу отсортировать список, если я мог бы вставить первый элемент в отсортированных хвосты.)

Я использовал «вставить», который thehelper функция.

Однако он переполняется. Кто-нибудь сказал мне, в чем проблема?

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)) ;; 

Answer 1

Эта линия выглядит неправильно меня:

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

Мне кажется, что вы знаете, ваш ys сортируются (по предположению индукции). Поэтому вы должны сравнивать n с ys, а не ys друг против друга. Если вы выберете эту линию, все будет улучшаться.

Для чего это стоит, я подозреваю, что вам нужно всего лишь иметь два случая в вашем match. Я не понимаю, почему вам нужно рассматривать список из 1 элемента иначе, чем любой другой ненулевой список.

Answer 2

Опять же, у меня есть предложения стиль:

• Вы должны отделить две функции sort и insert, потому что это сделало бы его более удобным для чтения, а также потому, что функция insert может быть полезен сам по себе.
• Почему вы даете кортеж в качестве аргумента функции insert? В OCaml можно использовать currying и написать insert x l вместо insert(x,l). Это позволит вам выполнять частичное приложение.
• Почему вы ограничиваете тип своей функции int list -> int list. Функции в OCaml могут быть полиморфными, поэтому ваша функция должна иметь более общий тип 'a ist -> 'a list.

Вот код, который Вы получаете все эти поправки:

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) 

Answer 3

Всегда задавая такие вопросы, это трудно для людей, чтобы читать такой код и в основном они будут игнорировать этот пост. Как @Thomash сказал, прежде всего, попытайтесь разделить на более мелкие функции, таким образом, легче видеть, где он терпит неудачу.

вы можете "отлаживать с глазом" это:

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 []