7

彼らが言うように、「真のクイックソートはその場でソートします」 . したがって、quicksortの標準的な短い Haskell コードは、

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

結局のところ、どのアルゴリズム/計算プロセスを記述しているのでしょうか?

それは間違いなくTony Hoare が考案したものではなく、その最も決定的な機能であるインプレース パーティショニング アルゴリズムが欠けています。

（答えはよく知られているかもしれませんが、まだSOではありません）。

訂正: この質問は実際には重複しています: 結局のところ、答えはSO で知られています: cf. 疑似クイックソート時間の複雑さ。

4

3 に答える 3

12

リンクリストのクイックソートです。

うん、これはクイックソートであり、インプレースではありません。リンクリストのデータ構造に一致するように低レベルの実装を変更しながら、クイックソートの高レベルのアルゴリズムに一致します。これが、リンクリストのクイックソートである理由です。

「本当のクイックソートはインプレースで行われる」よりも、「クイックソートは元々インプレースで機能するように開発された」と言いたいです。最悪の場合の動作などを回避するためにピボットをランダムに選択するなど、クイックソートには多くのバリエーションがあります。これは、リンクリストのクイックソートの賢明で明確な定義です。

この定義は、英国の16歳の数学の学生にクイックソートを教える方法と完全に一致しています。（私たちはプログラミングではなくアルゴリズムを教えています。）インプレースは目的と設計を非常に曖昧にします。そのため、関数型プログラミングやリンクリストを教えることから何百万マイルも離れているにもかかわらず、その詳細を教えません。（これは、破壊的な更新アレイがある場合に、ペアスワッピングトリックインプレースアルゴリズムが最適であるという事実を変えるものではありません。）

この定義には、2つのサブリストに対してリストを2回トラバースするため、時間のペナルティがあります。これをフィルターではなくパーティションに書き換えることは確かに可能ですが、ここでの基本的なアルゴリズムであるクイックソートを変更するのではなく、最適化することを主張します。

于 2013-02-09T10:10:23.207 に答える
1

すべてのインプレースアルゴリズムは、可変状態がモナドの背後に隠されているHaskellでの「儀式」を必要とします。上記のアルゴリズムはクイックソートであり、インプレースではありません。

于 2013-02-09T10:11:34.707 に答える
1

意図した答え (ここから) は、これが「本当に森林伐採された木の種類」であるということです。実は haskellwikiでも言及されています。

于 2013-02-09T14:39:25.110 に答える