次のような宿題があります (炎上しない/心配しないでください。宿題をするように頼んでいるわけではありません)。
二分探索木を使ったクイックソート法を使って数値の集合をソートするプログラムを書きなさい。推奨される実装は、再帰アルゴリズムを使用することです。
これは何を意味するのでしょうか？これまでの私の解釈は次のとおりです。以下で説明するように、どちらにも欠陥があると思います。
A. ユーザーから数値の配列 (整数など) を取得します。配列に対して通常のクイックソート アルゴリズムを使用してそれらをクイックソートします。次に、ものを二分探索木に入れ、配列の中間要素をルートにします。
B. ユーザーから数値を取得し、二分探索木の標準的なプロパティを使用して、それらを 1 つずつ直接ツリーに入れます。ツリーは「ソート」されています。すべてがうまくいっています。
これが私が混乱している理由です。オプション 'A' は、割り当てが要求するすべてのことを行いますが、それは二分木に関する宿題であるため、最後に最後にスローするほど二分木をあまり使用しません。これは、主なトピックがクイックソートではなくバイナリ ツリーであるため、意図した演習は「A」ではなかったと思います。
しかし、オプション 'B' はそれほど優れているわけではなく、クイックソートをまったく使用しません! だから、私は混乱しています。
ここに私の質問があります：
解釈がオプション「A」の場合は、そう言ってください。質問はありません。お時間をいただきありがとうございます。さようなら。
解釈がオプション「B」の場合、二分木に値を挿入するために使用されるソート方法がクイックソートと同じなのはなぜですか? どちらも (私がこれまでに学んだ形式で) 再帰分割統治戦略を使用し、入力を 2 つに分割するという事実を除けば、本質的に似ているようには見えません。
解釈が違うなら…どうすればいいの？