0

non-in-placeOCamlで選択ソートのバージョンを実装しました。

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

私の考えは、リストで最小項目のリストを見つけるたびに（値が重複している場合）、これmin listを結果リストに追加してから、リストの残りの部分でfinding_minをやり直すというものです。

List.filterを除外するために使用するmin_listので、結果のリストは次のリストになりますfind_min。

私の実装は非常に複雑で、Javaインプレースバージョンの選択ソートよりもはるかに複雑であることがわかりました。

それを改善するための提案はありますか？

4

1 に答える 1

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 []
于 2013-02-21T22:26:46.413 に答える