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

ハンドル名
件名
Link

>>う、確かに難しかったかも知れません(書くのはともかく読むのは)。
>>
>>　1.最初の要素をピボットにして、
>>　　残りの部分をピボット未満の要素のリスト(left)とピボット以上の要素のリスト(right)に分割する
>>　2.それぞれをソートする
>>　3.leftと最初の要素とrightをこの順に繋げる
>>
>>ということをやっています。
>>＃ それぞれを関数化すべきでしたね。
>>＃ ちなみに簡単だと思った理由は(ループが1重は冗談として)分割した後の領域の境界について考える必要がないからです
>
>解説ありがとうございます。
>簡単かどうかは置いといて、結局やっていることは
>アルゴリズム的には、配列と同様なことをやっているようですね。
>但し、配列とリンクリストは要素へのアクセス方法(の実装)は
>違いますが。
>
>>まあ、クイックソートは最悪の場合 O(n^2) になってしまうわけで、
>>ランダムアクセスできないとどうしても、
>>それを避けるために書いたコードのせいで定数項が大きくなってしまいそうです。
>>＃ gccのSTLの実装ではランダムアクセスイテレータにしかできないことばっかりやってたり
>>
>>リンクリストの場合はデータ構造を直接いじってマージソートしてしまった方が速いでしょうしね(std::listは実際にそうなっていますが)。
>
>確かに、std::listは、ソート用の自前のメンバ関数を持っていましたね。
>
>>＃ ちなみに上で説明した方法もデータ構造を直接いじっています
>>＃ ですから、std::sortでは同じことは出来ません
>>
>>
>>>NykRさんのサンプルの計算量はいまいち良く分かりませんでした。
>>
>>平均(のオーダー)は O(n log n) ですが最悪だと O(n^2)です。
>
>結局、std::listで、std::sortが使えないのは、実装がstd::listだけ
>特殊扱いになってしまうのでできないということですね。
>containerによって場合分けするなら、配列と同様な計算量で
>実装できるから問題ない訳で、std::sortは、
>汎用的な実装をしているというだけですね。
>汎用的と言っても、配列(系)の実装を想定しているだけだと思いますが。
>
>>＃ リストの最も簡単で速いソート方法は配列にコピーしてqso(略
>
>配列へのコピー時間はなしにしても、list#sortよりも早いのですか？
>qsoってqsort()のことですか？
>

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

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