Просто мои ноги были мокрые в алгоритме сортировки с Haskell. Я реализовал insert-sort и merge-sort
insert_sort :: (Ord a, Show a) => [a] -> [a]
insert_sort keys = foldr f [] keys
where f key [] = [key]
f key acc = insert key acc
insert y [] = [y]
insert y (x:xs)
| x < y = x : insert y xs
| otherwise = y : x : xs
merge_sort :: (Ord a, Show a) => [a] -> [a]
merge_sort (x:[]) = [x]
merge_sort keys = merge (merge_sort (take len keys)) (merge_sort (drop len keys))
where len = length keys `div` 2
merge :: [a] -> [a] -> [a]
merge (x:xs) [] = (x:xs)
merge [] (y:ys) = (y:ys)
merge (x:xs) (y:ys) = if x <= y
then x : merge (xs) (y:ys)
else y : merge (x:xs) ys
Вот как я сравнил их эффективность:
insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int]
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int]
Оба из них начинают печатать результаты после короткой задержки, но сортировка слияния выполняется намного быстрее. Как мы знаем, merge-sort намного быстрее, чем сортировка вставки для больших наборов данных. Я думал, что это будет показано тем, как они дают результаты (например, длинная задержка по сравнению с короткими), а не то, как они печатают результаты. Это потому, что я использую foldr в insert-sort? Что за сценой?
EDIT: спасибо ребята. Я слышал о ленивой оценке, так как я начал изучать Haskell, но все-таки понял это. Кто-нибудь проиллюстрирует немного больше небольшим набором данных, скажем [5,2,6,3,1,4]? Как можно выводить результаты до завершения сортировки с помощью foldr, так как наконец появляются первые элементы?
