特例についてのクイックソートとマージーソートの質問

-3

私はクイックソートで分かりますが、私は確認をしたいと思いますが、ちょっと混乱しています。特例についてのクイックソートとマージーソートの質問

最初に並べ替えたののn個の項目にQuicksortを適用するとします。少なくとも1つの要素がtheta（n）の比較に関与するでしょうか？どのくらいでしょうか最初にランダムなオーダー？

最初に並べ替えられた注文ののn個の項目にMergesortを適用するとします。少なくとも1つの要素がtheta（n）の比較に関与するでしょうか？どのくらいでしょうか最初にランダムなオーダー？

クイックソートのエントリレベルでは、ピボット値がn-1個の他の要素と比較されます。マージソートでは、最後のパスで1つの要素との比較の可能な最悪のケースが発生し、サイズ1のランとサイズn-1のランをマージし、再びn-1回の比較を行います。 – rcgldr

マージベストケース： "ジッパーのようなマージ"： "すべての"要素は* 2つの他の要素と比較されます。 – greybeard

ピボット選択ルールを知らなくてもクイックソートに関する質問に答えられるとは限りません。 –

-1

両方にあてはまる、プリソートされているかどうか。

それについて考える：彼らは実際にはすでにソートされていることを確認するためにも、場合にのみ、あなたは、少なくとも一度* N項目を比較することなく並べ替えることはできません。

（あなたには、いくつかのサブシーケンスは、すでにあなたは、汎用のソートに仮定することはできません最終的な順序でソートされていることを先験的を知っている限り）...

私はしていない限りあなたの質問を誤解しました。同じ要素がN比較に使用されている場合は、求めていますか？

2017-10-03 06:35:00

あなたの最後の文が残っているのを恐れています。 –

答えて