K.Maebashi's BBS 削除ページ

以下の投稿を削除します。

[840] Re:マスタングさんへ
返信
投稿者:NykR
2007/02/20 02:13:25

勘違いがあったので訂正します。 >>ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 ピボットを選ぶのは関数呼び出し1回につき1度だけなので、頭から順にアクセスしていってもオーダーは変わりませんね。 という訳で「ワーストケースに対応できない」というのはこの意味では嘘でした。 >>実装はリンクリストの方がむしろ簡単だと思います。 > >クイックソートがリンクリストで実装できるのは知りませんでしたが、 >私はNykRさんの実装が難しくて理解できませんでした う、確かに難しかったかも知れません(書くのはともかく読むのは)。  1.最初の要素をピボットにして、   残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する  2.それぞれをソートする  3.leftと最初の要素とrightをこの順に繋げる ということをやっています。 # それぞれを関数化すべきでしたね。 # ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです >STLのsort()はランダムアクセスイテレータが必要ですが、 >私のイメージは、listはクイックソートに対して、 >実行効率の面で現実的ではないからできないのだと思っています。 >実装が簡単だというのも重要だと思いますが、 >(STLは)ライブラリなのであくまでもパフォーマンスが問題で、 >やはりリンクリストでは配列と同等のパフォーマンスが >でないのではないでしょうか? まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、 ランダムアクセスできないとどうしても、 それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。 # gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。 # ちなみに上で説明した方法もデータ構造を直接いじっています # ですから、std::sortでは同じことは出来ません >NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。 # リストの最も簡単で速いソート方法は配列にコピーしてqso(略
パスワード:

管理者削除