K.Maebashi's BBS

>う、確かに難しかったかも知れません(書くのはともかく読むのは)。 > >　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()のことですか？