6

HaskellのWebサイトには、次のクイックソート実装の例があります。

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

サイトに説明がありますが、見なかった質問がいくつかあります...

  • 再注文のために2つの要素で実際の比較/交換はどこで行われますか？これは、「Ord」（順序付けられた）型定義自体によって処理されますか？それで、タイプは注文されるというこの条件を強制しますか？
  • 'greater'フィルターはアイテム'>= p'（ピボット）を定義します。したがって、' ++ [p ]' アイテム？
4

4 に答える 4

33
  1. There is no swap, because this is not the (almost-)in-place version of QS. Instead, new lists are built and then concatenated — comparison is done when lesser and greater are created, with <, >= — Ord is a typeclass restricting a to be orderable — if it wasn't used, you wouldn't be able to use < or >=.
  2. No, because the pivot is not part of xs — pattern match splits input list into p and xs.

Here's crappy ASCII visualisation:

                                qs [5, 5, 6, 3, 1]
                                          |
                         qs [3, 1]   ++  [5] ++ qs [5, 6]
                             |            |       |
                  qs [1] ++ [3] ++ qs []  |    qs [] ++ [5] ++ qs [6]
                             |            |       |
                           [1, 3]    ++  [5]  ++ [5, 6]
                             \            |        /
                              \-------------------/
                                        |
                                  [1, 3, 5, 5, 6]
于 2012-04-16T02:18:25.083 に答える
17

並べ替えのために 2 つの要素で実際の比較/交換が行われるのはどこですか? Ordこれは、 (順序付けられた) 型定義自体によって処理されますか。では、型はこの順序付けの条件を強制するのでしょうか?

とはOrdどういう意味ですか?

Ordjust は、aそれ自体と比較可能であること、またはより厳密に言えば>、 、<、およびなどの操作==を に対して定義する必要があることを意味しaます。メソッドの制約と考えることができます。

それで、注文はどこで行われますか？

そして答えは最後のパターンです:

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

実行時に、プログラムは配列を取得しようとしており、配列は次の 2 つのパターンのいずれかを満たす必要があります。

パターン 1#: 空の場合、関数は同じ空の配列を返し、停止します。

パターン 2#: 空でない、つまりp末尾の配列に先頭要素が追加されているxs。そのような場合、関数はp中央に配置され、 のすべての要素がの左側 ( で定義されているように)xsより小さく、 のすべての要素がの右側に配置されます。さらに、関数は最終的にそれ自体 (つまり、同じ関数) を(上で定義したように の左側の配列) および(上で定義したように右側の配列) に適用するように指示されます。側面plesserpxsppquicksortlesserpgreaterp）。ご覧のとおり、サイズがゼロの配列が残り、パターン 1# が関数を終了するまで、これが続きます。

最後に、これらの再帰呼び出しが終了するたびに、関数は配列を返します。

sortedlesser ++ p ++ sortedgreater

ここで、 は on をsortedlesser適用した結果の配列であり、 はquicksortonlesserを適用しsortedgreaterた結果の配列です。quicksortgreater

ちょっと待って…pを何度も複製していませんか？

'greater' 述語は項目 '>= p' (ピボット) を定義するので、'++ [p ]' アイテム？

いいえ、これはパターン マッチングの仕組みではありません。その内のすべての要素xsが以上であると言っていpます。定義上p、それ自体は から外れていxsます。pinの重複がある場合xs、それらは右側に配置されます。この選択により、元の配列の自然な順序が維持されることに注意してください。

于 2012-04-16T02:35:11.833 に答える
8

これをさらに短く、より効率的に書くことができることに注意してください（partition元のリストを1回だけスキャンするため）

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where (lesser, greater) = partition (< p) xs
于 2012-04-16T06:48:00.303 に答える
2

1 行だけが必要な場合:

qsortOneLine s = case s of{[]->[];(x:xs)->qsortOneLine [y | y<-xs, y<x] ++ x : qsortOneLine [y | y<-xs, y>=x]}

よりパフォーマンスの高いコードが必要な場合:

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' [] y     = y
qsort3' [x] y    = x:y
qsort3' (x:xs) y = part xs [] [x] []  
      where
         part [] l e g = qsort3' l (e ++ (qsort3' g y))
         part (z:zs) l e g 
             | z > x     = part zs l e (z:g) 
             | z < x     = part zs (z:l) e g 
             | otherwise = part zs l (z:e) g

http://en.literateprograms.org/Quicksort_(Haskell )

于 2012-07-16T09:34:19.247 に答える