これは私が最近インターネットで見つけたインタビューの質問です：
整数配列を入力として受け取り、最大値を返す関数を実装する場合、この関数を実装するためにバブルソートまたはマージソートを使用しますか？配列サイズが1000未満の場合はどうなりますか？1000より大きい場合はどうなりますか？
これは私がそれについてどう考えるかです：
まず、上記の関数を実装するために並べ替えを使用するのは本当に奇妙です。配列を1回調べて、最大の配列を見つけることができます。次に、2つから選択する必要がある場合は、バブルソートの方が適しています。バブルソート手順全体を実装する必要はありませんが、最初のパスを実行するだけで済みます。時間と空間の両方でマージソートよりも優れています。
私の答えに間違いはありますか？私は何かを逃しましたか？
それはトリックの質問です。最大値（または、中央値の検索を含む、任意のkのk番目の値）が必要な場合は、完全に優れたO(n)アルゴリズムがあります。並べ替えは時間の無駄です。それが彼らが聞きたいことです。
あなたが言うように、最大化のためのアルゴリズムは本当に些細なことです。このような質問に答えるには、クイックセレクトアルゴリズムを用意し、値のリストを変更して常に最大値を迅速に生成できるようにする必要がある場合に備えて、ヒープデータ構造を提案できる必要があります。
アルゴリズムをグーグルで検索しました。バブルソートは、一度だけ実行する必要があるという最大の利点があるため、どちらの状況でも勝ちます。マージソートは、最大数を計算するだけでよいため、ショートカットをカットすることはできません。マージはリストの長さを取り、中央を見つけます。次に、中央より下のすべての数値が左と比較され、上のすべての数値が右と比較されます。比較する一意のペアを作成するのとは反対に。配列に残っているすべての数について、同じ数の比較を行う必要があることを意味します。それに加えて、各数値は2回比較されるため、両方の比較で配列の最小数が削除される可能性があります。多くの状況で2つの比較を行った後、配列内の数が1つ少ないことを意味します。バブルが支配するだろう
最初に私はあなたが言ったことすべてに同意しますが、おそらくそれはアルゴリズムの時間計算量と入力サイズがどのように最速になる大きな要因であるかを知ることについて尋ねています。
バブルソートはであり、マージソートはです。したがって、小さなセットではそれほど違いはありませんが、多くのデータではバブルソートがはるかに遅くなります。O(n2)O(nlogn)
最大の部分を除けば、バブルソートは漸近的に遅くなりますがn、新しい配列のマージ/作成を必要としないという点で、小さい場合には大きな利点があります。一部の実装では、これによりリアルタイムで高速化される場合があります。
最悪の場合、最大のuを見つけるために必要なパスは1つだけなので、配列全体をトラバースするだけでよいので、バブルの方が優れています。
マージソートは、コンピューターが要素をソートするのに簡単で、バブルソートよりもソートにかかる時間が短くなります。マージソートの最良のケースはでn*log2nあり、最悪のケースはn*log2nです。バブルソートでは、最良の場合はO(n)であり、最悪の場合はO(n2)です。