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