K.Maebashi's BBS

勘違いがあったので訂正します。 >>ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 ピボットを選ぶのは関数呼び出し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(略