Сортировка Фон-Неймана
Может кто-нить нормально описать процесс сортировки Фон-Неймана? Или дать ссылку на нормальное(понятное и не требующее читать 50 страниц до этого момента) описание? Желательно не кодом, а текстом.
Цитата: Imperator_of_RusFed
Может кто-нить нормально описать процесс сортировки Фон-Неймана?
А разве сабж существует в природе?
[QUOTE=<SCORP>;279265]http://www.cyberforum.ru/post13442.html[/QUOTE]
Насколько я понял, там описан алгоритм для массивов длины 2^n, а что с другими делать?
Насколько я понял, там описан алгоритм для массивов длины 2^n, а что с другими делать?
Цитата: Imperator_of_RusFed
Насколько я понял, там описан алгоритм для массивов длины 2^n, а что с другими делать?
Как вариант, разбить массив на несколько, размерностями 2^n + 2^m + 2^k + ... (т. е. для массива, например, из 11 элементов получаем массивы 8 элементов + 2 + 1), отсортировать их, потом слить.
Вариант, но потом слитый все равно неосортированный получится.
Вот код на ocaml(ml):
let rec merge a b =
match (a, b) with
(a1::al, b1::bl) ->
if a1 <= b1 then
a1:: (merge al b)
else
b1:: (merge a bl)
|(a1::al, []) -> a
|([], b1::bl) -> b
|_ -> [];;
let rec step l =
match l with
l1::l2::ls -> merge l1 l2:: (step ls)
|l -> l;;
let listify l =
map (fun x -> [x]) l;;
let vnsort l =
let rec sh s =
match s with
[] -> []
|[s1] -> s1
|_ -> sh (step s) in
sh (listify l);;
Добрые люди подкинули
Вот код на ocaml(ml):
let rec merge a b =
match (a, b) with
(a1::al, b1::bl) ->
if a1 <= b1 then
a1:: (merge al b)
else
b1:: (merge a bl)
|(a1::al, []) -> a
|([], b1::bl) -> b
|_ -> [];;
let rec step l =
match l with
l1::l2::ls -> merge l1 l2:: (step ls)
|l -> l;;
let listify l =
map (fun x -> [x]) l;;
let vnsort l =
let rec sh s =
match s with
[] -> []
|[s1] -> s1
|_ -> sh (step s) in
sh (listify l);;
Добрые люди подкинули
Цитата: Imperator_of_RusFed
Вариант, но потом слитый все равно неосортированный получится.
Так надо сливать в упорядоченный массив. :rolleyes: Тем же алгоритмом, которым, согласно вышеприведённой ссылке, сливаются "четвёрки в восьмёрки".