algorithm - クイックソートは「適応型」で「オンライン」ですか?

Question

つまり、既にソートされたリストが与えられた場合、クイックソートはより良いパフォーマンスを発揮しますか? なぜそうなるのかはわかりませんが、アルゴリズムを正確に理解していない可能性があります。

また、ソート中に新しいデータをリストに追加している間、クイックソートを「続行」できますか? アルゴリズムが「機能する」には、最初にすべてのデータの完全なセットが必要なようです。

Answer 1

既にソートされたリストが与えられた場合、クイックソートはより良いパフォーマンスを発揮しますか?

いいえ、実際には、すでにソートされた (またはほぼソートされた) リストが通常教えられる (最初の要素をピボットとして使用する) 方法は、最悪のケースです。ただし、中央またはランダムな要素をピボットとして使用すると、これを軽減できます。

ソート中に新しいデータをリストに追加している間、クイックソートを「続行」できますか?

いいえ、あなたの直感は正しいです。最初からデータ セット全体が必要です。

Answer 2

すでにソートされたリストが与えられた場合、クイックソートはより良いパフォーマンスを発揮しますか

クイックソートのパフォーマンスは、各ステップでのピボット要素の選択に大きく依存すると思います。選択されたピボット要素がリスト内の最小または最大の要素である可能性が高い場合は最悪です

ソート中に新しいデータをリストに追加している間、クイックソートは「続行」しますか?

はい、クイックソートは適応的ではありません。それがクイックソートの特性です。