1

私は数行で挿入ソートとクイックソートを実装することができましたが、選択ソートとマージソートは依然として頭痛の種です;)

selectionsort [] = []

selectionsort (x:xs) =
    let (minimum, greater) = extractMinimum x [] xs
    in  minimum : selectionsort greater

extractMinimum minimumSoFar greater [] = (minimumSoFar, greater)

extractMinimum minimumSoFar greater (x:xs)
    | x < minimumSoFar = extractMinimum x (minimumSoFar:greater) xs
    | otherwise        = extractMinimum minimumSoFar (x:greater) xs

extractMinimum標準ライブラリで利用できる関数のようなものはありますか? (a -> a -> Bool/Ordering) -> [a] -> (a, [a])運がないのでフーグリングしてみました。

mergesort [ ] = [ ]

mergesort [x] = [x]

mergesort xs =
    let (left, right) = splitAt (length xs `div` 2) xs
    in  merge (mergesort left) (mergesort right)

merge xs [] = xs

merge [] ys = ys

merge xxs@(x:xs) yys@(y:ys)
    | x < y     = x : merge  xs yys
    | otherwise = y : merge xxs  ys

繰り返しますが、merge自分で作成する必要がありますか? それとも既存のコンポーネントを再利用できますか? Hoogle は について有用な結果をくれませんでした(a -> a -> Bool/Ordering) -> [a] -> [a] -> [a]。

4

2 に答える 2

2

標準ライブラリには何もありませんが、少なくともhackagemergeのパッケージによって提供されていますが、そのような単純な関数の依存関係を引き込む価値があるかどうかはわかりません。

でも、

merge xxs@(x:xs) yys@(y:ys)
    | x < y     = x : merge  xs yys
    | otherwise = y : merge xxs  ys

は非安定ソートを生成します。安定ソートを取得するには、配置する条件を にするx必要がありますx <= y。

についてextractMinimumも、何も見つかりませんでしたが、別の定義を提供できます。

extractMinimum :: Ord a => a -> [a] -> (a,[a])
extractMinimum x = foldl' select (x, [])
  where
    select (mini, greater) y
      | y < mini  = (y, mini:greater)
      | otherwise = (mini, y:greater)

の良い定義selectionSortは

import Data.List -- for unfoldr

selectionSort :: Ord a => [a] -> [a]
selectionSort = unfoldr getMin
  where
    getMin [] = Nothing
    getMin (x:xs) = Just $ extractMinimum x xs
于 2012-10-06T15:44:37.283 に答える
0

選択ソートに関する私の提案:

import Data.List

selectionsort xs = unfoldr f xs where
    f [] = Nothing
    f xs = Just $ extractMinimum xs

extractMinimum (x:xs) = foldl' f (x,[]) xs where
  f (minimum, greater) x | x < minimum = (x, minimum : greater)
                         | otherwise = (minimum, x : greater)
于 2012-10-06T16:28:47.273 に答える