В очередной лекции упоминалась сортировка выбором, и я решил сделать её реалзизацию в функциональном стиле на OCaml, насколько это вообще возможно.
В этот раз у меня были такие цели:
- написать проверочный код в чисто императивном стиле;
- написать вариант со списками и с рекурсией, пусть и не хвостовой.
В этот раз решение без разделения на разные программы и передачу данных через stdin и stdout.
Итак, первый и самый простой вариант - императивный:
let imp_sel_sort lst =
let data = List.to_array lst in
let last_index = Array.length data - 1 in
for i = 0 to last_index do
let ind = ref i in
for j = (i + 1) to last_index do
if data.(j) < data.(!ind) then
ind := j;
done;
if !ind <> i then
Array.swap data i !ind;
done;
Array.to_list data
Тут всё, как в описании алгоритма. Ищем минимальный элемент и ставим его в очередную позицию. Для поиска индекса использовал изменяемое значение let ind = ref i in.
Следующая реализация - сортировка списка с рекурсией и разбором списка до элементарных значений.
let fun_sel_sort lst =
let rec find_min = function
| [] -> assert false
| [hd] -> (hd, [])
| hd :: tl -> (
let hd', tl' = find_min tl in
if hd < hd' then
hd, hd' :: tl'
else
hd', hd :: tl'
)
in
let rec sort _lst =
let m, rest = find_min _lst in
match rest with
| [] -> [m]
| _ -> m :: sort rest
in
match lst with
| [] | [_] -> lst
| lst -> sort lst
В этом варианте я искал минимальный элемент в остатке списка и потом конструировал из них отсортированный список, вызывая рекурсивно сортировку с остатком списка без этого элемента. Для такого финта ушами мне понадобилось, чтобы функция поиска минимального элемента возвращала и сам элемент и список, в котором его нет. По сути, мне приходилось разбивать список на ряд целых чисел, а потом собирать его обратно по стеку вызовов.
Пока писал функциональный вариант, решил попробовать написать новый вариант императивной сортировки, но при этом ограничиться только одной изменяемой переменной - массивом, а индекс минимального значения сделать обычной переменной, без ref.
let imp_rec_sel_sort lst =
let data = List.to_array lst in
let last_index = Array.length data - 1 in
for i = 0 to last_index do
let min_index =
let rec find imin current =
if current > last_index then
imin
else begin
let imin = match compare data.(imin) data.(current) with
| 1 -> current
| _ -> imin
in
if current = last_index then
imin
else
find imin (current + 1)
end
in
find i (i + 1)
in
if min_index <> i then
Array.swap data i min_index;
done;
Array.to_list data
Для запуска всех этих функций мне потребовался небольшой тестовый код, который позволил мне проверить, что всё работает так, как я ожидал:
let list2str x = x |> List.to_string ~f:string_of_int
let () =
(* Код для первоначальной проверки работоспособности *)
imp_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
fun_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
imp_rec_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
Полный листинг программы с тестом и выводом ошибок:
open Core.Std
let fun_sel_sort lst =
let rec find_min = function
| [] -> assert false
| [hd] -> (hd, [])
| hd :: tl -> (
let hd', tl' = find_min tl in
if hd < hd' then
hd, hd' :: tl'
else
hd', hd :: tl'
)
in
let rec sort _lst =
let m, rest = find_min _lst in
match rest with
| [] -> [m]
| _ -> m :: sort rest
in
match lst with
| [] | [_] -> lst
| lst -> sort lst
let imp_sel_sort lst =
let data = List.to_array lst in
let last_index = Array.length data - 1 in
for i = 0 to last_index do
let ind = ref i in
for j = (i + 1) to last_index do
if data.(j) < data.(!ind) then
ind := j;
done;
if !ind <> i then
Array.swap data i !ind;
done;
Array.to_list data
let imp_rec_sel_sort lst =
let data = List.to_array lst in
let last_index = Array.length data - 1 in
for i = 0 to last_index do
let min_index =
let rec find imin current =
if current > last_index then
imin
else begin
let imin = match compare data.(imin) data.(current) with
| 1 -> current
| _ -> imin
in
if current = last_index then
imin
else
find imin (current + 1)
end
in
find i (i + 1)
in
if min_index <> i then
Array.swap data i min_index;
done;
Array.to_list data
let list2str x = x |> List.to_string ~f:string_of_int
let rec test deep =
let render_error lst =
[
"Error!";
"Origin: " ^ (lst |> list2str);
"Imperative: " ^ (lst |> imp_sel_sort |> list2str);
"Functional: " ^ (lst |> fun_sel_sort |> list2str);
"Imperative with recursion: " ^ (lst |> imp_rec_sel_sort |> list2str);
]
in
let rec create_random_list num =
match num with
| 0 -> []
| _ -> Random.int 10:: create_random_list (num - 1)
in
let random_list = create_random_list deep in
let imp_sorted = imp_sel_sort random_list in
if imp_sorted <> (fun_sel_sort random_list) || imp_sorted <> (imp_rec_sel_sort random_list) then
random_list |> render_error |> List.fold ~init:"" ~f:(fun accum s -> accum ^ s ^ "\n")
else if deep > 0 then
test (deep - 1)
else
"Ok"
let () =
(*
(* Код для первоначальной проверки работоспособности *)
imp_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
fun_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
imp_rec_sel_sort [3; 4; 8; 1; 2]
|> list2str
|> printf "%s\n";
*)
test 100 |> printf "%s"
Заключение
Практической ценности у fun_sel_sort и imp_rec_sel_sort нет. Я их написал просто в качестве упражнения. Это похоже на code golf, когда пытаются решить задачу, использовав при написании кода наименьшее количество символов. Так и здесь, это просто разминка для мозгов.
