[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(略