K.Maebashi's BBS 投稿フォーム

ハンドル名
件名
Link

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

spamよけのため、ここに「ほげぴよ」と入力してください。

削除パスワード : クリック！