15

O(n log n)クイックソートには平均的な時間計算量があることを私は知っています。関数型言語の簡潔さを示すためによく使用される疑似クイックソート（これは、十分に遠くから見た場合にのみクイックソートであり、適切に高いレベルの抽象化を備えています）は次のとおりです（Haskellで提供）。

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

さて、私はこれに問題があることを知っています。これに関する最大の問題は、それがその場でソートされないことです。これは通常、クイックソートの大きな利点です。それが問題ではなかったとしても、リストを分割するときにリストの2つのパスを実行する必要があり、後でそれをつなぎ合わせるためにコストのかかる追加操作を行うため、通常のクイックソートよりも時間がかかります。さらに、ピボットとして最初の要素を選択することは最良の選択ではありません。

しかし、そのすべてを考慮しても、このクイックソートの平均時間計算量は標準のクイックソートと同じではありませんか？つまりO(n log n)？アペンドとパーティションは、非効率的であっても、線形時間計算量を持っているためです。

4

6 に答える 6

9

この「クイックソート」は、実際には森林破壊されたツリーソートです：http： //www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

二分木は不均衡であるため、検索ツリーを構築するためのO（N ^ 2）最悪の場合とO（N * Log N）平均の場合の複雑さ。

foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l)

取得アルゴリズムには、最悪の場合はO（N ^ 2）、平均の場合はO（N * Log N）の複雑さがあります。

バランスのとれた：

Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537
Prelude> length . quicksort . take 4000 . rnds $ 1
4000
(0.08 secs, 10859016 bytes)
Prelude> length . quicksort . take 8000 . rnds $ 1
8000
(0.12 secs, 21183208 bytes)
Prelude> length . quicksort . take 16000 . rnds $ 1
16000
(0.25 secs, 42322744 bytes)

あまりバランスが取れていない：

Prelude> length . quicksort . map (`mod` 10) $ [1..4000]
4000
(0.62 secs, 65024528 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..8000]
8000
(2.45 secs, 241906856 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..16000]
16000
(9.52 secs, 941667704 bytes)
于 2012-07-06T07:08:15.890 に答える
5

平均時間計算量はまだであるというあなたの仮定に同意しますO(n log n)。私は専門家ではなく、100％確信していますが、これらは私の考えです。

これは、インプレースクイックソートの擬似コードです:( l =1およびr=配列の長さでクイックソートを呼び出します）

Quicksort(l,r)  
--------------
IF r-l>=1 THEN  
    choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r}   
    order the array-segment x_l,...x_r in such a way that  
        all elements < x are on the left side of x // line 6  
        all elements > x are on the right side of x // line 7  
    let m be the position of x in the 'sorted' array (as said in the two lines above)  
    Quicksort(l,m-1);  
    Quicksort(m+1,r)  
FI

次に、平均時間計算量分析は、このアルゴリズムの主要な操作として6行目と7行目の「<」比較を選択することによって推論し、最終的に平均時間計算量はO（n log n）であるという結論に達します。「配列セグメントx_l、... x_rを...のように並べ替える」という行のコストは考慮されていないため（境界を見つけたい場合は、時間計算量分析では主要な操作のみが重要です）、私は思います「それを分割するときにリストの2つのパスを実行する必要があるため」は問題ではありません。また、Haskellバージョンはこのステップで約2倍の時間がかかるためです。同じことが付録操作にも当てはまり、これが漸近コストに何も追加しないことに同意します。

アペンドとパーティションは、非効率的であっても、線形時間計算量を持っているためです。

便宜上、これにより時間計算量のコストに「n」が加算され、「O（n log n + n）」になると仮定します。そのnlogn> nには自然数oが存在し、oより大きいすべての自然数が当てはまるため、n log n+nを上から2nlog nまで、下からnlognまで推定できます。 n log n + n = O（n log n）。

さらに、ピボットとして最初の要素を選択することは最良の選択ではありません。

平均的なケース分析では、配列内の要素が均一に分布していると想定しているため、ここではピボット要素の選択は重要ではないと思います。配列内のどの場所から選択する必要があるかわからないため、ピボット要素（リストのどの場所から取得するかとは関係なく）がi番目に小さい要素であるこれらすべてのケースを考慮する必要があります。リストの、i = 1...rの場合。

于 2012-07-06T07:25:47.257 に答える
4

Ideone.comで実行時間テストを提供できます。これは、（++）ベースのバージョンと、 Landeiの回答からのアキュムレータ手法を使用したバージョン、および1つを使用した別のバージョンの両方で多かれ少なかれ線形の実行時間を示しているようです。-スリーウェイパーティショニングを渡します。順序付けられたデータでは、これはすべてのデータで2次またはさらに悪化します。

-- random:   100k        200k         400k         800k
-- _O    0.35s-11MB  0.85s-29MB   1.80s-53MB   3.71s-87MB   n^1.3  1.1  1.0
-- _P    0.36s-12MB  0.80s-20MB   1.66s-45MB   3.76s-67MB   n^1.2  1.1  1.2
-- _A    0.31s-14MB  0.62s-20MB   1.58s-54MB   3.22s-95MB   n^1.0  1.3  1.0
-- _3    0.20s- 9MB  0.41s-14MB   0.88s-24MB   1.92s-49MB   n^1.0  1.1  1.1

-- ordered:   230     460     900     1800
-- _P        0.09s   0.33s   1.43s    6.89s                 n^1.9  2.1  2.3
-- _A        0.09s   0.33s   1.44s    6.90s                 n^1.9  2.1  2.3
-- _3        0.05s   0.15s   0.63s    3.14s                 n^1.6  2.1  2.3

quicksortO xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ [x] ++ go [y | y<-xs, y>=x]

quicksortP xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ (x : go [y | y<-xs, y>=x])

quicksortA xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)

quicksort3 xs = go xs [] where
  go     (x:xs) zs = part x xs zs [] [] []
  go     []     zs = zs
  part x []     zs a b c = go a ((x : b) ++ go c zs)
  part x (y:ys) zs a b c =
      case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

経験的な実行時の複雑さO(n^a)は、ここでは次のように推定されますa = log( t2/t1 ) / log( n2/n1 )。ideoneは時折遠く離れているため信頼性が低いため、タイミングは非常に概算ですが、時間の複雑さをチェックするにはそれで十分です。

したがって、これらのデータは、1パスパーティションが2パススキームよりも1.5倍から2倍高速であり、使用して(++)も速度が低下することはないことを示しているようです。つまり、「追加操作」は「コストがかかる」わけではありません。二次動作または（++）/ appendは、都会の神話のようです—もちろんHaskellのコンテキストでは（編集： ...つまり、ガード再帰/末尾再帰のモジュロコンのコンテキストで;この回答を参照）（更新： as user：AndrewC は説明します、それは実際には左の折り畳みで二次です;右の折り畳み(++)で使用されるとき線形です;これについての詳細こことここ）。

後で追加：安定させるために、スリーウェイパーティショニングクイックソートバージョンもトップダウン方式でパーツを構築する必要があります。

q3s xs = go xs [] where
  go     (x:xs) z = part x xs  go  (x:)  (`go` z)
  go     []     z = z
  part x []      a  b  c = a [] (b (c []))
  part x (y:ys)  a  b  c =
      case compare y x of
                  LT -> part x ys  (a . (y:))  b  c
                  EQ -> part x ys  a  (b . (y:))  c
                  GT -> part x ys  a  b  (c . (y:))

（パフォーマンスはテストされていません）。

于 2012-07-07T08:36:22.567 に答える
2

これにより実行時の複雑さがどれだけ改善されるかはわかりませんが、アキュムレータを使用することで、高価なものを回避できます(++)。

quicksort xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)
于 2012-07-06T10:15:25.323 に答える
0

はい、このバージョンは従来のバージョンと同じ漸近的な複雑さを持っています-線形時間partitionを次のように置き換えます：2パス（<および>=）、および追加の線形時間++（線形再割り当て/コピーを含む）があります。したがって、インプレースパーティションよりもかなり悪い定数係数ですが、それでも線形です。アルゴリズムの他のすべての側面は同じであるため、「真の」（つまりインプレース）クイックソートのO（n log n）平均ケースを与える同じ分析がここでも当てはまります。

于 2012-09-03T21:07:01.613 に答える
0

配列とリストの両方で機能する真のO（n log n）クイックソートをここで探してください： http ：//citeseer.ist.psu.edu/viewdoc/download？doi = 10.1.1.23.4398＆rep = rep1＆type=pdf それはCommon Lispでの実装は非常に簡単で、多くの商用Lispのソート実装よりも優れています。

于 2012-09-02T20:09:52.557 に答える