2

これは、「それほど速くない」と見なされるクイックソートの実装です。

qSort :: Ord a => [a] -> [a]
qSort [] = []
qSort (p:xs) = (qSort $ filter (< p) xs) ++ (qSort $ filter (== p) xs) ++ [p] ++ (qSort $ filter (> p) xs)

main = print $ qSort [15, 11, 9, 25, -3]

それにもかかわらず、それを行うために必要な比較の数を数えることは可能ですか? filter (< p) xsandのサイズを数えようとしましたfilter (> p) xsが、必要なものではないことがわかりました。

更新：

問題は時間の複雑さではなく、まさに比較の数を数えることです。

4

4 に答える 4

3

Monad Newb が回答で提案したように、理論的に質問を考えることは、おそらくアルゴリズムが実際に何をするかを考える最良の方法です。

Stateもちろん、比較をモナドに貼り付けるというばかげた方法もあります。これは、比較関数の呼び出しごとに力ずくでカウントします。アクションの使用に注意してくださいcount。これは、述語を、その述語の各呼び出しを追跡するアクションに変換し、それをその引数に適用するだけです。

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad.State

qSortM :: Ord a => [a] -> State Int [a]
qSortM [] = return []
qSortM (p:xs) = do h <- (qSortM =<< filterM (count (< p)) xs)
                   e <- (qSortM =<< filterM (count (== p)) xs)
                   t <- (qSortM =<< filterM (count (> p)) xs)
                   return $ h ++ e ++ [p] ++ t
               where count :: (a -> Bool) -> (a -> State Int Bool)
                     count p a = modify (+1) >> return (p a)

qSort :: Ord a => [a] -> ([a],Int)
qSort l = runState (qSortM l) 0

main :: IO ()
main = print $ (qSort [15, 11, 9, 25, -3])

Stateこれは実際にはひどい Haskell であり、モナドなしで、再帰関数を使用するだけで表現できます。このように書くと良い練習になります。確かに、Stateモナドのバージョンは、命令的なバックグラウンドを持つ人々にとってより直感的に理解できるでしょう。

> qSort [10,9..1]
([1,2,3,4,5,6,7,8,9,10],90)

> qSort [15,11,9,25,-3]
([-3,9,11,15,25],14)
于 2013-07-25T14:43:34.643 に答える
1

式を評価しましょうqSort [15, 11, 9, 25, -3]:

qSort [15, 11, 9, 25, -3]
    = qSort (15:[11, 9, 25, -3])
    = (qSort $ filter (< 15) [11, 9, 25, -3])
      ++ (qSort $ filter (== 15) [11, 9, 25, -3])
      ++ [p]
      ++ (qSort $ filter (> 15) [11, 9, 25, -3])
    = (qSort [11, 9, -3]) ++ (qSort []) ++ [p] ++ (qSort [25])

ここまで到達するために、12 回の比較を行いました。の残りのアプリケーションをqSort同様の方法で評価できます。

ここではいわゆる純粋関数型プログラミングを使用しているため、この種の置換は有効であることに注意してください。副作用がないため、任意の式を同等の式に置き換えることができます。

于 2013-07-25T14:22:19.837 に答える
1

この数を計算する関数を書くだけです。それぞれfilter p xsがlength xs比較を実行します。それだけです。

現在、コードはパーティションを実行するために 3 つのパスを実行します。1 回のパスで 3 方向のパーティションを実行するように書き直すことができます。パスの数をパラメーターにすることができます。

もう 1 つの問題は、すべての等しい要素を含むことが既にわかっている中間セクションの不必要な並べ替えです。この不必要な並べ替えが実行されるかどうかを知らせるために、これもパラメーターにすることができます。

_NoSort = False
_DoSort = True

qsCount xs n midSortP = qs 0 xs id     -- return number of comparisons that 
 where                                 -- n-pass `qSort xs` would perform
   qs !i []     k = k i
   qs !i (p:xs) k = 
     let (a,b,c) = (filter (< p) xs, filter (== p) xs, filter (> p) xs)
     in qs (i+n*length xs) a (\i-> g i b (\i-> qs i c k))
   g i b k | midSortP  = qs i b k 
           | otherwise = k i

ご覧のとおり、1 回のパスよりも 3 回のパスの方が 3 倍多くの比較が必要であり、中間の並べ替えは、リストに 2 つ以上の等しい要素がある場合にのみ違いを生むことができます。

*Main> qsCount ( concat $ replicate 4 [10,9..1]) 3 _NoSort
630
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 3 _DoSort
720
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 1 _NoSort
210
*Main> qsCount ( concat $ replicate 4 [10,9..1]) 1 _DoSort
240
*Main> qsCount [5,3,8,4,10,1,6,2,7,9] 1 _NoSort
19
*Main> qsCount [5,3,8,4,10,1,6,2,7,9] 1 _DoSort
19
*Main> qsCount (replicate 10 1) 1 _NoSort
9
*Main> qsCount (replicate 10 1) 1 _DoSort
45
*Main> qsCount [15, 11, 9, 25, -3] 3 _DoSort
21
于 2013-07-25T19:14:13.087 に答える