OCaml에서 비공식 선택 정렬을 구현하는 더 간단한 방법은 없습니까?

Question

OCaml에서 non-in-place 선택 정렬 버전을 구현했습니다.

---

let sort compare_fun l = 
    let rec find_min l' min_l origin_l = 
     match l' with 
    | [] -> 
     if min_l = [] then (min_l, l') 
     else 
     let min = List.hd min_l 
     in 
     (min_l, List.filter (fun x -> if x != min then true else false) origin_l) 
    | x::tl -> 
     if min_l = [] then 
     find_min tl [x] origin_l 
     else 
     let c = compare_fun (List.hd min_l) x 
     in 
     if c = 1 then 
      find_min tl [x] origin_l 
     else if c = 0 then 
      find_min tl (min_l @ [x]) origin_l 
     else 
      find_min tl min_l origin_l 
    in 
    let rec insert_min l' new_l = 
     match l' with 
    | [] -> new_l 
    | _ -> 
     let (min_l, rest) = find_min l' [] l' 
     in 
     insert_min rest (new_l @ min_l) 
    in 
    insert_min l [];; 

---

내 생각은 목록에서 때마다 내가 (중복 값의 경우) 최소 항목의 목록을 찾은 다음 finding_min을 다시 실행, 결과 목록이 min list을 추가 할 것입니다 나머지 목록에서는

List.filter을 사용하여 min_list을 걸러 내기 때문에 결과 목록은 다음 find_min의 목록이됩니다.

필자의 구현은 매우 복잡하며 Java 인플레 이스 버전의 선택 정렬보다 훨씬 복잡합니다.

의견을 제안 하시겠습니까?

Answer 1

편집 : 여기에 훨씬 더 나은 구현의 : 여기 http://rosettacode.org/wiki/Sorting_algorithms/Selection_sort#OCaml

내 자신의 더 형편 구현입니다 당신은 시작할 수 있습니다

(* partial function - bad habit, don't do this. *) 
let smallest (x::xs) = List.fold_right (fun e acc -> min e acc) xs x 

let remove l y = 
    let rec loop acc = function 
    | [] -> raise Not_found 
    | x::xs -> if y = x then (List.rev acc) @ xs else loop (x::acc) xs 
    in loop [] l 

let selection_sort = 
    let rec loop acc = function 
    | [] -> List.rev acc 
    | xs -> 
     let small = smallest xs in 
     let rest = remove xs small in 
     loop (small::acc) rest 
    in loop []