K.Maebashi's BBS

>クイックソートは、アルゴリズムそのものにはランダムアクセスは不要です。 >ただ、ピボットを選ぶときにランダムアクセスできないとワーストケースに対応できないので、その意味では配列の方が良いと言えるかもしれません。 >実装はリンクリストの方がむしろ簡単だと思います。 クイックソートがリンクリストで実装できるのは知りませんでしたが、 私はNykRさんの実装が難しくて理解できませんでした (いやみではありません。能力的な問題です)。 STLのsort()はランダムアクセスイテレータが必要ですが、 私のイメージは、listはクイックソートに対して、 実行効率の面で現実的ではないからできないのだと思っています。 実装が簡単だというのも重要だと思いますが、 (STLは)ライブラリなのであくまでもパフォーマンスが問題で、 やはりリンクリストでは配列と同等のパフォーマンスが でないのではないでしょうか？ NykRさんのサンプルの計算量はいまいち良く分かりませんでした。 クイックソートのアルゴリズムにランダムアクセスがなくても 実装可能だと言うのは了解しました。